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 momojiang at 2014-04-09 23:40:33 on Problem 1091
#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