題目鏈接：

xdoj 1243 ckj老師愛數學 傳送門

大致題意是已知z，求滿足x^2+y^2=z^2的整數解x,y的個數。這道題是在暑期集訓結束的組隊賽碰到的，原題貌似是BZOJ上求半徑為r的圓上整點的個數。

乍一看題，臥槽z的范圍怎么那么大，暴力肯定要超時的啊！然后就開始暴力打表找規律= =。。。

想知道正解的話建議去搜BZOJ原題的題解，這里只有我打表找到規律的做法（正解我也不會2333）。

博主首先直接暴力打出了z從1開始到100+左右的表，觀察規律。當然這個規律并不算很明顯，至少博主是看了很久的。最開始發現，答案為12時的z都是4的倍數+1且為質數，而這些質數的倍數貌似也滿足某種規律？然后就實驗了很多組數據，首先驗證了4的倍數+1且為質數的z的答案都是12。然后以該類數為基礎，推斷出這些數的倍數與這些數所具有的聯系，最后總結出整體的規律。（這種做法真的挺亂搞的，全靠人品、YY和找規律= =）

1、當z為0時，答案為1，z為1時，答案為4。

2、z不為1時，將z分解為質因數的冪相乘的形式，p[]數組存質因數，對應的e[]數組存冪次。

若z沒有%4余1的質因數，則答案為4，若z含有若干個%4余1的質因數，對于每一個p都有（2*e+1）個4，將所有符合條件（%4余1）的質數的（2*e+1）乘起來，最后所得的結果再乘以4即為答案。（可能表述的不是很清楚，看代碼吧）

另外，比賽時分解的時候板子敲錯了，但是數據不怎么強，居然過了。當然賽后不久發現了，略一修改成功過了BZOJ原題，想來雖不是正解，這樣寫也是可以的。

AC代碼如下：（對于質數來說，顯然直接判斷要比分解來得快，所以直接可以輸出答案）

#include #include #include #include #include using namespace std; #define N 1000010 int cnt1,cnt2,prime[N],p[100],e[100],ans[100]; bool notprime[N]; void init(){cnt1=0;notprime[1]=1;for(int i=2;i<N;i++){if(notprime[i]==false)prime[cnt1++]=i;for(int j=0;j<cnt1&&prime[j]*i<N;j++){notprime[prime[j]*i]=true;if(i%prime[j]==0){break;}}} } void fenjie(int n){cnt2=0;memset(p,0,sizeof(p));memset(e,0,sizeof(e));for(int i=0;i<cnt1&&prime[i]<=n;i++){if(n%prime[i]==0){p[cnt2]=prime[i];while(n%prime[i]==0){n/=prime[i],e[cnt2]++;}cnt2++;}}if(n>1){p[cnt2]=n,e[cnt2++]=1;} } bool isprime(int n){if(n==1)return false;for(int i=2;i<=sqrt(n);i++){if(n%i==0)return false;}return true; } int main(){init();int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);if(n==1){printf("1\n");continue;}bool c=isprime(n);if(n%4==1&&c){printf("12\n");}else if(c){printf("4\n");}else{fenjie(n);int s=1;memset(ans,0,sizeof(ans));for(int i=0;i<cnt2;i++){if(p[i]%4==1){ans[i]=e[i]*2+1;s*=ans[i];}}if(s==0)printf("4\n");elseprintf("%d\n",s*4);}}return 0; }

總結

以上是生活随笔為你收集整理的xdoj 1243 ckj老师爱数学的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。