--- 恢复内容开始 ---
链接: https://ac.nowcoder.com/acm/contest/330/E
思路: 很简单, 2^n, 但是要注意 n 可以取到 10 的 10 万次方, 此时要用到指数循环节降幂或者十进制快速幂 (或者 python)
题解:
- #include <iostream>
- #include <string>
- #define ll long long
- const ll mod = 1e9+7;
- using namespace std;
- ll quickPow(ll a,ll b)
- {
- ll ans = 1;
- a %= mod;
- while(b)
- {
- if(b&1) ans = (ans * a) % mod;
- a = a * a % mod;
- b>>= 1;
- }
- return ans;
- }
- ll euler(ll n)
- {
- ll res = n;
- for(int i = 2; i*i <n; i++)
- {
- if(n % i == 0)
- res = res / i * (i-1);
- while(n%i==0)
- n /= i;
- }
- if(n> 1)
- res = res / n * (n-1);
- return res;
- }
- int main()
- {
- string s1,s2;
- while(cin>>s1>>s2)
- {
- ll length = s1.size(),n = 0,p;
- //p = mod - 1;
- p = euler(mod);
- for(int i = 0; i < length; i++)
- {
- n =(n * 10 + (s1[i] - '0')) % p;
- }
- cout<<quickPow(2,n)<<endl;
- }
- return 0;
- }
- (抄的大佬的代码)
备注: 大佬写的是指数循环节, 用到欧拉降幂公式
接下来放出 python 代码:
1 print(pow(2,int(input().split()[0]),10**9+7))
吐槽: 我被震撼了, python 太强大了.
总结 -- 欧拉降幂公式
--- 恢复内容结束 ---
来源: http://www.bubuko.com/infodetail-2940989.html