首页 > 代码库 > 数论某些题目

数论某些题目

平面上有一个圆, 圆心坐标为(0,0),半径为n. 问圆周上有多少个整点. 整点的定义即x,y坐标均为整数的点.

 

做题过程:思考后感觉有点难度,可能用到一些奇怪的知识,于是决定去看题解;

题解:

1.一般人都能想到x2+y2=r2这一点,但是仅想到这一点并没什么用;

2.变形:

   移项得:r2-x2=y2

   得y2=(r-x)(r+x)

   设d=gcd((r-x),(r+x))

   则设A=(r-x)/d,B=(r+x)/d

   代入原式得 y2=ABd2

   因为gcd(A,B)=1

   所以A,B均为完全平方数

   设a2=A,b2=B

   可得a2+b2=2r/d

3.得到上面的式子,d很显然是2r的约数,可以枚举d;

在枚举d时,可以枚举a,算出b,若gcd(a,b)等于1,则ans++即可;

个人理解:实际上它这个最后的式子相比于最初的式子有什么优点呢?

第一个是r的次数由2次方变成了一次方,于是就可以发现原来的一个O(n)级别的算法成了根号级别的算法;

本质上是通过数学运算除去原本枚举时的无用状态;

代码:

技术分享
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<ctime>
 6 #include<algorithm>
 7 #include<cstdlib>
 8 #include<map>
 9 #include<set>
10 #include<vector>
11 #include<queue>
12 using namespace std;
13 #define FILE "dealing"
14 #define LL long long 
15 #define up(i,j,n) for(int i=j;i<=n;i++)
16 #define pii pair<int,int>
17 #define piii pair<int,pair<int,int> >
18 template<typename T> inline bool chkmin(T &a,T b){return a>b?a=b,true:false;}
19 namespace IO{
20     char *fs,*ft,buf[1<<15];
21     inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
22     inline int read(){
23         int x=0,ch=gc();bool f=0;
24         while(ch<0||ch>9){if(ch==-)f=1;ch=gc();}
25         while(ch<=9&&ch>=0){x=(x<<1)+(x<<3)+ch-0;ch=gc();}
26         return f?-x:x;
27     }
28 }using namespace IO;
29 namespace OI{
30     LL n;
31     LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
32     LL cnt=0;
33     void slove(){
34         scanf("%lld",&n);
35         for(LL d=1;d*d<=2*n;d++){
36             if(!(2*n%d)){
37                 for(LL a=1;a*a<=(n/d);a++){
38                     LL b=(LL)sqrt(2.0*n/d-a*a);
39                     if(a*a+b*b==2*n/d&&gcd(a,b)==1&&a!=b)cnt++;
40                 }
41                 d=2*n/d;
42                 for(LL a=1;a*a<=(n/d);a++){
43                     LL b=(LL)sqrt(2.0*n/d-a*a);
44                     if(a*a+b*b==2*n/d&&gcd(a,b)==1&&a!=b)cnt++;
45                 }
46                 d=2*n/d;
47             }
48         }
49         cnt=4*cnt+4;
50         printf("%lld\n",cnt);
51     }
52 }
53 int main(){
54     freopen(FILE".in","r",stdin);
55     freopen(FILE".out","w",stdout);
56     using namespace OI;
57     slove();
58     return 0;
59 }
View Code

 

数论某些题目