結果

問題 No.781 円周上の格子点の数え上げ
ユーザー akakimidoriakakimidori
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0