Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 今天携程的原题。

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: