今天做了一題仿自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
//直接計算可得...