HDU - 4704 Sum——费马小定理

HDU - 4704 Sum——费马小定理

ans=2^(n-1)%mod = 2^((n-1)%(mod-1)+(n-1)/(mod-1)*(mod-1))%mod=2^((n-1)%(mod-1))%mod*2^((n-1)/(mod-1)*(mod-1))%mod=2^((n-1)%(mod-1))%mod

对于(n-1)%(mod-1),可以先算出n%(mod-1),那么(n-1)%(mod-1) = (n%(mod-1)-1+(mod-1))%(mod-1)

#include #include #include #include #include using namespace std;const int maxn = 2e5;const int mod = 1e9 + 7;string s;int n;long long ipow(long long a, long long x) { long long ans = 1; while (x) { if (x & 1) ans = ans * a % mod; a = a * a % mod; x >>= 1; } return ans;}int main() { while (cin >> s) { long long num = 0; for (int i = 0; i < s.size(); i++) num = (num*10+(s[i]-'0'))%(mod-1); num = (num-1+mod-1) % (mod-1); cout << ipow(2, num) << endl; } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。