首页 > 代码库 > 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;}
View Code

 

BZOJ1408 NOI2002 Robot 快速幂+欧拉函数