Calculation HDU - 2837 欧拉降幂 2019-10-09 算法竞赛 暂无评论 63 次阅读 ## 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2837](http://acm.hdu.edu.cn/showproblem.php?pid=2837) Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x). Input The first line contains a single positive integer T. which is the number of test cases. T lines follows.Each case consists of one line containing two positive integers n and m. Output One integer indicating the value of f(n)%m. Sample Input ``` 2 24 20 25 20 ``` Sample Output ``` 16 5 ``` ## 思路 欧拉降幂公式$a^{b}$% p = $a^{ b \% \varphi( p)+ \varphi( p)}$$,b\geqslant \varphi (p)$ 注意：快速幂取模的时候 res < mod则不管，res >= mod 时 res=res%mod+mod. 这样返回进行下一层运算时相当于用了欧拉降幂公式 ## 代码 ```javascript #include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m; ll phi(ll x) { ll res=x; for(ll i=2; i*i<=x; i++) { if(x%i==0) res=res/i*(i-1); while(x%i==0) x/=i; } if(x>1) res=res/x*(x-1); return res; } ll mpow(ll x,ll n,ll mod) { ll res=1; if(x>mod) x=x%mod+mod; while(n) { if(n&1) { res=res*x; if(res>mod) res=res%mod+mod; } x=x*x; if(x>mod) x=x%mod+mod; n>>=1; } return res; } ll f(ll n,ll m) { if(n==0) return 1; if(n<10) return n; ll Phi=phi(m); return mpow(n%10,f(n/10,Phi),m); } int main() { int t; cin>>t; while(t--) { cin>>n>>m; cout<<f(n,m)%m<<endl; } } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭