HDU4704 Sum(大数取模,深刻理解费马小定理)
发布时间:2020-12-14 04:51:22 所属栏目:大数据 来源:网络整理
导读:Sum Simple Input 2 3 Simple Output 2 4 思路:原题把人坑死,原来交换位置算新的一种.插板法 C(1,n)+C(2,n)+······+C(n,n) = 2^n. 即求2^(n-1),但是n极大,这里取模运算就用到了大数取模和费马小定理. 假如a,p互质,则a^(p-1)%p == 1恒成立,所以此
SumSimple Input 2 3 Simple Output 2 4 思路:原题把人坑死,原来交换位置算新的一种.插板法 C(1,n)+C(2,n)+······+C(n,n) = 2^n. 即求2^(n-1),但是n极大,这里取模运算就用到了大数取模和费马小定理. 假如a,p互质,则a^(p-1)%p == 1恒成立,所以此题是不是可以利用这一性质呢. 因为2^n %p== 2^(p-1)*2(n-(p-1))%p == 2^(p-1)%p*2(n-(p-1))%p == 1*2(n-(p-1))%p. 所以此题我们只要计算n%(p-1)就好,n这么大怎么模p-1呢? 1234%m == (((1*10+2)*10+3)*10+4?)%m?== (((1%m*10+2)%m*10+3)%m*10+4)%m 解决啦! 代码: #include<bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define mod 1000000007 using namespace std; typedef long long ll; const int maxn = 1e6+5; const double esp = 1e-7; const int ff = 0x3f3f3f3f; map<int,int>::iterator it; char s[maxn]; ll big_mod() { ll ans = s[0] - '0'; int len = strlen(s); for(int i = 1;i< len;i++) ans = (ans*10+s[i]-'0')%(mod-1); return ans; } ll quick_pow(ll x,ll y) { ll ans = 1; while(y) { if(y&1) ans = (ans*x)%mod; y>>= 1; x = (x*x)%mod; } return ans; } int main() { while(~scanf(" %s",s)) { ll m = big_mod(); cout<<quick_pow(2,m-1)<<endl; } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |