hdu1452Happy2004数论

hdu1452
思路&＃xff1a;看到题目2004的x次方&＃xff0c;1 <&＃61; x<&＃61; 10000000&＃xff0c;而取模的数只有29&＃xff0c;一看到这么大的范围就应该想到不可能直接让你去做幂方运算&＃xff0c;因此&＃xff0c;仔细看题给出的2004的因子&＃xff0c;可以发现&＃xff0c;2004&＃61;223167&＃xff0c;这几个都是质数&＃xff0c;然后结合约数和定理可知&＃xff0c;sum&＃61;(2^0 &＃43; 2 ^ 1&＃43;…&＃43;2 ^(2x))(3 ^ 0 &＃43;3 ^ 1 &＃43;…&＃43;3 ^ x)(167 ^ 0 &＃43;167 ^1&＃43;… &＃43;167 ^ x)&＃xff0c;由等比数列前n项和公式可知sum&＃61;(2 ^ (2x&＃43;1) -1)((3 ^ (x&＃43;1)-1)/2)*((167 ^ (x&＃43;1) -1)/166)&＃xff0c;又因为167这个数也大了&＃xff0c;最后乘起来运算不够简便&＃xff0c;我们再仔细观察&＃xff0c;发现167和22模29的结果相同&＃xff0c;21和166模29的结果相同&＃xff0c;因此用22替换167&＃xff0c;21替换166&＃xff0c;运算量会小一点&＃xff0c;不然会wa&＃xff0c;我就是167提交&＃xff0c;结果wa的不明所以&＃xff0c;这题还要注意下除以2和除以21的运算不要直接除&＃xff0c;要先用费马小定理求2和21的逆元
ac代码 0ms

#pragma GCC optimize("O3")
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define For(i,j,k) for(register int i&＃61;(j);i<(k);i&＃43;&＃43;)
#define MEM(a,b) memset(a,b,sizeof(a))
#define sc(a) scanf("%d",&a)using namespace std;typedef int ll;
const ll mod&＃61;29;ll quick_pow(ll x,ll y)
{ll ans&＃61;1;while(y){if(y&1)ans&＃61;(ans*x)%mod;x&＃61;(x*x)%mod;y>>&＃61;1;}return ans%mod;
}ll quick_mul(ll x,ll y)
{ll ans&＃61;0;while(y){if(y&1)ans&＃61;(ans&＃43;x)%mod;x&＃61;(x&＃43;x)%mod;y>>&＃61;1;}return ans%mod;
}int main()
{ll n;while(~sc(n)&&n){ll inv1&＃61;quick_pow(2,mod-2);ll inv2&＃61;quick_pow(21,mod-2);ll a&＃61;(quick_pow(2,2*n&＃43;1)-1)%mod;ll b&＃61;(quick_pow(3,n&＃43;1)-1)*inv1%mod;ll c&＃61;(quick_pow(22,n&＃43;1)-1)*inv2%mod;ll d&＃61;quick_mul(b,c)%mod;ll ans&＃61;quick_mul(a,d)%mod;printf("%d\n",ans%mod);}return 0;
}