結果
問題 | No.781 円周上の格子点の数え上げ |
ユーザー |
![]() |
提出日時 | 2019-01-11 21:56:37 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 870 bytes |
コンパイル時間 | 1,303 ms |
コンパイル使用メモリ | 29,952 KB |
実行使用メモリ | 40,916 KB |
最終ジャッジ日時 | 2024-11-30 06:10:35 |
合計ジャッジ時間 | 1,882 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<stdio.h>#include<stdlib.h>#define MAX(a,b) ((a)>(b)?(a):(b))typedef struct farey{int a,b,c,d;} farey;void run(void){int x,y;scanf("%d%d",&x,&y);int *cnt=(int *)calloc(y+1,sizeof(int));int k;for(k=1;k*k<=y;k++) cnt[k*k]+=4;for(k=1;2*k*k<=y;k++) cnt[2*k*k]+=4;farey stack[32];int top=0;stack[top++]=(farey){0,1,1,1};while(top>0){farey f=stack[--top];int p=f.a+f.c;int q=f.b+f.d;if(p*p+q*q>y) continue;for(k=1;k*k*(p*p+q*q)<=y;k++){cnt[k*k*(p*p+q*q)]+=8;}if(f.b<=f.d){stack[top++]=(farey){f.a,f.b,p,q};stack[top++]=(farey){p,q,f.c,f.d};} else {stack[top++]=(farey){p,q,f.c,f.d};stack[top++]=(farey){f.a,f.b,p,q};}}int max=cnt[x];for(k=x+1;k<=y;k++) max=MAX(max,cnt[k]);printf("%d\n",max);}int main(void){run();return 0;}