首页 > 代码库 > BZOJ1408 NOI2002 Robot 快速幂+欧拉函数
BZOJ1408 NOI2002 Robot 快速幂+欧拉函数
题意：分别求所有质因数都不同且质因数个数为奇数个、偶数个的数的欧拉函数和，和质因数存在重复的数的欧拉函数和
题解：
说书题……前面一大串就是用一种比较有趣的语言定义欧拉函数。
显然我们只需要求出所有军人ans1和政客ans2，然后用求得的M减去独立数和就是学者的独立数和了。
由于善良的出题人已经帮我们把M给质因分解了，因此我们假定当前已经得到了ans1和ans2，那么根据欧拉函数的定义，ans1‘=ans1+ans2*(p-1),ans2‘=ans2+ans1*(p-1)，因为新加入的质因子会让奇偶互换。
由于e可能很大，所以用快速幂来算。
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int P=10000;const int MAXN=1000+2;int K,M=1,ans1=1,ans2,ans3;int Quick_Pow(int x,int y){ int t=(y&1?x:1); while(y>>=1){ x=(x*x)%P; if(y&1) t=(t*x)%P; } return t;}int main(){ cin >> K; for(int i=1,t1,t2,p,e;i<=K;i++){ scanf("%d %d",&p,&e); M=(M*Quick_Pow(p,e))%P; if(p==2) continue; t1=(ans1+ans2*(p-1))%P,t2=(ans2+ans1*(p-1))%P; ans1=t1,ans2=t2; } ans3=(M-ans1-ans2+2*P)%P,ans1--; cout << ans1 << endl << ans2 << endl << ans3 << endl; return 0;}
BZOJ1408 NOI2002 Robot 快速幂+欧拉函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。