Input

2

Output

2 Hint 1. For N = 2, S(1) = S(2) = 1.2. The input file consists of multiple test cases.

Sample Input

2

Sample Output

2

這道題的公式非常簡單，就是求2^(N-1) %1e9+7

由于N實在是太大了，不能直接求快速冪，考慮到2^x % MOD是有循環節的，因此使用歐拉降冪公式a^x ≡a^(x mod?(p)+?(p)) (mod p)

?

#include <iostream> #include <cstdio> #include <cstring> using namespace std; typedef long long int64; int64 MOD = 1e9 + 6; char str[200007]; int64 mod_pow(int64 x,int64 n){int64 ans = 1;while(n){if(n & 1){ans = (ans * x) % (MOD + 1);}x = (x * x) % (MOD + 1);n >>= 1;}return ans % (MOD + 1); } int main(){while( cin>>str) {int len = strlen(str);int64 mod = 0;for(int i = 0; i < len;i++){mod *= 10;mod += str[i] - '0';mod %= MOD;}mod = (mod - 1)%MOD;printf("%lld\n",mod_pow(2,mod + MOD) ); }return 0; }

總結

以上是生活随笔為你收集整理的Summer Training day4 欧拉降幂的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。