Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

今天携程的原题。

Posted by yygy at 2014-04-10 20:23:16 on Problem 1091
In Reply To:感觉容斥原理那个公式变成乘法比较好写 Posted by:momojiang at 2014-04-09 23:40:33
> #include <cstdio>
> using namespace std;
> long long quickpow(long long m,long long n){
> 	long long res=1;
> 	while(n){
> 		if(n&1)
> 			res*=m;
> 		m*=m;
> 		n>>=1;
> 	}
> 	return res;
> }
> long long ans(long long n,long long m){
> 	long long f=quickpow(m,n);
> 	long long x=m;
> 	for(long long i=2;i*i<=x;i++){
> 		if(m%i==0){
> 			long long q=quickpow(i,n);
> 			f=f/q*(q-1);
> 			while(m%i==0)
> 				m/=i;
> 		}
> 	}
> 	if(m>1)
> 		f=f/quickpow(m,n)*(quickpow(m,n)-1);
> 	return f;
> }
> int main(){
> 	long long n,m;
> 	while(scanf("%I64d%I64d",&n,&m)!=EOF)
> 		printf("%I64d\n",ans(n,m));
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator