题目描述
求一个给定的圆,在圆周上有多少个点的坐标是整数。
输入格式
正整数。
输出格式
整点个数。
题目解析
题目十分清爽简洁,然而我WA了无数次……
题目要求圆上的整点个数。首先坐标轴一定有4个点,其次四个象限的整点个数一定是相同的,所以只要讨论第一象限内部的情况。
问题转化为求方程的正整数解的组数。利用平方差公式,可得
,设
,则
两数一定是完全平方数。不妨设
,显然
。将两式相加,得
,于是枚举
的约数
,具体方法为枚举
,每次处理
的两个约数
和
,分别枚举
,计算出
,若满足条件
则
加1。最终答案为
。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
/************************************************************** Problem: 1041 User: frank_c1 Language: C++ Result: Accepted Time:100 ms Memory:1284 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define lowbit(x) (x)&(-x) #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ LL gcd(LL a,LL b) {return b==0?a:gcd(b,a%b);} int main() { LL r; read(r); int cnt=0; for(LL d=1;d*d<=2*r;d++) { if((2*r)%d!=0) continue; for(LL u=1;u*u<=2*r/d;u++) { LL v=(LL)sqrt(2*r/d-u*u); if(u>=v || u*u+v*v!=2*r/d) continue; if(gcd(u,v)==1) cnt++; } if(d*d==2*r) continue; for(LL u=1;u*u<=d;u++) { LL v=(LL)sqrt(d-u*u); if(u>=v || u*u+v*v!=d) continue; if(gcd(u,v)==1) cnt++; } } printf("%d\n",(cnt+1)*4); return 0; } |