fafu -1002 简单吗? - 快速取模 （a*b）%mod

2019-04-13 13:18发布

站内文章 / 模拟电子
15655 0 1230
题目 ： 本题类似与 快速幂 的写法，只是略微不同。

快速幂模板： int QuickPow(int a,int b) { int res = 1; while( b ) { if( b&1 ) { res = ( res * a)% MOD; } a = (a*a)%MOD; b >>= 1; } return res; }
快速取模模版： typedef long long lLL; LL solve( LL a,LL b,LL mod) { LL res = 0; while( b ) { if( b&1 ) res = (res+a)%mod; b>>=1; a = ( a<<1)%mod; } return res%mod; }
理论上这题这样写 a <<1 可能会爆long long 但是还是AC了，估计数据有点水~
a*b --》可以看作 有 b 个 a 相加。 用二分的思想来做，b一直除以2，那么a就要乘以2，才能达到原来等式的平衡。 b&1 如果b是奇数，那么a 就要领出来再操作一次。 #include #include using namespace std; typedef long long LL; LL a,b,mod; LL solve( LL a,LL b,LL mod) { LL res = 0; if( a >b )//稍微做了一个优化 也不知道起多大作用 { a = a^b; b = a^b; a = a^b; } while( b ) { if( b&1 ) res = (res+a)%mod; b>>=1; a = ( a<<1)%mod; } return res%mod; } int main() { while( cin>>a>>b>>mod) { cout<


热门文章