求大数的n次方对m取模（欧拉降幂）

2019-04-13 21:10发布

站内文章 / 模拟电子
15115 0 1135
博主链接 #include #include using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 1e5 + 10; const int MOD = 1e9 + 7; char s[MAXN]; long long phi(long long x) { long long ret = x; for (int i = 2; i * i <= x; ++i) if (x % i == 0) { ret -= ret / i; while (x % i == 0) x /= i; } if (x > 1) ret -= ret / x; return ret; } ll mpow(ll a, ll n, ll m) //a ^ n % m { ll t = 1; while (n) { if (n & 1) t = (t * a) % m; a = (a * a) % m, n >>= 1; } return t; } int main() { #ifdef LOCAL //freopen("C:/input.txt", "r", stdin); #endif int T; cin >> T; while (T--) { ll n = 0, p = phi(MOD); scanf("%s", s); for (int i = 0; s[i]; i++) n = (n * 10 + s[i] - '0') % p; n += p - 1; ll ans = mpow(2, n, MOD); cout << ans << endl; } return 0; }

热门文章