具体使用方法:
题目链接:
http://acm.fzu.edu.cn/problem.php?pid=1759
题目大意:
欧拉降幂裸题
(为啥用 dd 输入是对的, 用 %lld 输入却是 TLE..)
AC 代码:
- #include<iostream>
- #include<stdio.h>
- #include<bitset>
- #include<cstring>
- using namespace std;
- # define ll __int64
- # define LL_inf (1ll<<60)
- # define inf 0x3f3f3f3f3
- const int maxn = 2e6+20;
- ll ph(ll x)
- {
- ll res=x,a=x;
- for(ll i=2; i*i<=x; i++)
- {
- if(a%i==0)
- {
- res=res/i*(i-1ll);
- while(a%i==0)
- a/=i;
- }
- }
- if(a>1ll)
- res=res/a*(a-1ll);
- return res;
- }
- ll qsm(ll t1,ll t2,ll mod)
- {
- ll ans=1ll;
- while(t2)
- {
- if(t2&1)
- ans=ans*t1%mod;
- t1=t1*t1%mod;
- t2>>=1;
- }
- return ans%mod;
- }
- //ll cal(ll n){
- //if(n==1)return 0;
- //ll tmp=ph(n);
- //return qsm(2ll,cal(tmp)+tmp,n);
- //}
- char str[maxn];
- int main()
- {
- ll a,c;
- while(scanf("%I64d %s %I64d",&a,str,&c)!=EOF)
- {
- ll tmp=ph(c);
- ll ans=0;
- int len=strlen(str);
- for(int i=0; i<len; i++)
- {
- ans=(ans*10+str[i]-'0')%tmp;
- }
- // ans+=tmp;
- printf("%lld\n",qsm(a,ans+tmp,c));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3090030.html