首页 > 代码库 > hdu--4549--费马小定理&快速幂&欧拉函数
hdu--4549--费马小定理&快速幂&欧拉函数
这题 蛮复杂的.
我自己做的时候 无法处理完 最后一步公式的转换 后来看到别人说这是 费马小定理 与 欧拉函数的思想下的转换
可是 我自己还推导不出来啊...
首先 你要发现f[n]=a^x * b^y其实指数x 与 y是fib数列中的f[n-1]与f[n]项( n>=1 并且数列是0 1 1 2 3 5 8 ...)
那么 其实题目就转换成了 f[n] = a^fib[n-1] * b^fib[n] % mod;
这边 不必要对于 a^fib[n-1]与 b^fib[n] 单独再在括号进行取模运算 因为Mod = 1000000007 太大了 即使单独取模 还是会存在溢出的可能 因为只要(mod-1)%mod = mod-1那么这 (mod-1)^2肯定溢出int了 所以 就直接用Long long就是了
然后我就是不会对于fib[n-1]进行化简取模了 因为不对它取模 肯定是溢出的 可是我想不明白 具体的MOD 应该取多少呢？
就去看了别人的解释 说是 费马小定理与欧拉函数的联系吧
当p是素数的时候 满足
a(p) ≡ a（mod p）
当p是素数的时候 并且gcd(a,p) == 1的时候 满足
a(p-1) ≡1（mod p）
还有一个就是 a( euler(p) ) ≡1（mod p）
当p是素数的时候 那么euler(p) 自然就是p-1了
然后 将2者联系起来 就可以化简为 a^fib(n-1) = a^( fib(n-1)%(mod-1) ) % (mod)
但是 这2者怎么联系 转换 我没求导出来 太渣了 烦.
1 #include <iostream> 2 using namespace std; 3 4 typedef long long LL; 5 const LL mod = 1000000007; 6 struct matrix 7 { 8 LL m[2][2]; 9 }base,ans;10 11 matrix multi( matrix& p , matrix& q , int col )12 {13 matrix temp;14 for( int i = 0 ; i<2 ; ++i )15 {16 for( int j = 0 ; j<col ; ++j )17 {18 temp.m[i][j] = 0;19 for( int k = 0 ; k<2 ; ++k )20 {21 temp.m[i][j] = ( temp.m[i][j] + p.m[i][k] * q.m[k][j] )%(mod-1);22 }23 }24 }25 return temp;26 }27 28 void fastMod( LL n )29 {30 while( n )31 {32 if( n&1 )33 {34 ans = multi( base , ans , 1 );35 }36 base = multi( base , base , 2 );37 n >>= 1;38 }39 }40 41 LL solve( LL x , LL n )42 {43 LL ans = 1;44 while( n )45 {46 if( n&1 )47 {48 ans = x * ans % mod;49 }50 n >>= 1;51 x = x * x % mod;52 }53 return ans;54 }55 56 int main()57 {58 cin.sync_with_stdio(false);59 LL a , b , n , var;60 while( cin >> a >> b >> n )61 {62 ans.m[0][0] = 1;63 ans.m[1][0] = 1;64 base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;65 base.m[1][1] = 0;66 if( !n )67 cout << a << endl;68 else if( n==1 )69 cout << b << endl;70 else if( n==2 )71 cout << (a*b%mod) << endl;72 else73 {74 fastMod( n-2 );75 a = solve( a , ans.m[1][0] );76 b = solve( b , ans.m[0][0] );77 var = a * b % mod;s78 cout << var << endl;79 }80 }81 return 0;82 }
hdu--4549--费马小定理&快速幂&欧拉函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。