今天做了一题仿自Google Code Jam Round 1 C. Numbers的题目...
大意是求高斯函数y=[(2^(0.5)+3^(0.5))^(2n)]%1024的值
以下是我的解题思路:
//高斯函数y=[pow(2,0.5)+pow(3,0.5)]^(2n)]
//y=[(5+2*pow(6,0.5))^n]
//添加项(5-2*pow(6,0.5))^n
//构造Y=(5+2*pow(6,0.5))^n+(5-2*pow(6,0.5))^n;
//由二项展开得Y是整数...
//因为0<(5-2*pow(6,0.5))<1,所以y=[pow(2,0.5)+pow(3,0.5)]^(2n)]=(5+2*pow(6,0.5))^n + (5-2*pow(6,0.5))^n - 1
//将y展开得y=2*(C0n*5^n+C2n*5^(n-2)(2*pow(6,0.5))^2+Cn4*5^(n-4)*(2*pow(6,0.5))^4+....)%1024
//分析得y=2*(C0n*5^n+C2n*5^(n-2)(2*pow(6,0.5))^2+Cn4*5^(n-4)*(2*pow(6,0.5))^4)%1024
//直接计算可得...