题解 P2508 [[HAOI2008]圆上的整点]

~~这是一道数学题~~ 高斯曾证明过这么一个东西$:$ > 设正整数$n=2^{a_0}p_1^{a_1}…p_s^{a_s}q_1^{b_1}…q_t^{b_t},$其中$p_1,…,p_s,q_1…q_t$是不同的质数$,p_i≡1\pmod{4}(1\leq i\leq s),q_j≡3\pmod{4}(1\leq j\leq t),$而$a_0,…a_s,b_1,…,b_t$是非负整数$.$则当$b_1,…,b_t$至少有一个为奇数时$,f(n)=0.$而当$b_1,…,b_t$都是偶数时$,f(n)=4(a_1+1)(a_2+1)…(a_s+1).$ 上述定理中$f(n)$函数表示方程$x^2+y^2=n$的正整数解个数$($证明过程略$,$太复杂$).$于是我们可以运用此定理$,$将题目中的$r$分解质因数$,$由于是$x^2+y^2=r^2,$所以$b_1…b_t$肯定都为偶数$,$答案为$4(2a_1+1)(2a_2+1)…(2a_s+1)$ $Pollard\_Rho,$复杂度是$\Theta(n^\frac{1}{4})(\text{就算r是1e+18都能过})$ $\mathbb{CODE:}$ ```cpp #include <bits/stdc++.h> #define int long long const int pri[]={2,3,5,7,11,13,17,23,29}; using std::vector; using std::sort; int n,i,j,cnt,ans=1; vector<int> v; inline void read(int &x) { short negative=1; x=0; char c=getchar(); while(c<'0' || c>'9') { if(c=='-') negative=-1; c=getchar(); } while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); x*=negative; } inline void print(int x) { if (x<0) putchar('-'),x=-x; if(x>9) print(x/10); putchar(x%10+'0'); } inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);} inline int ksc(int x,int y,int mod) { return (x*y-(long long)((long double)x/mod*y)*mod+mod)%mod; } inline int ksm(int a,int b,int m) { int ans=1; a%=m; while(b) { if(b&1) ans=ksc(a,ans,m); b/=2; a=ksc(a,a,m); } ans%=m; return ans; } inline bool MR(int x,int p) { if(ksm(x,p-1,p)!=1) return false; int k=p-1; while(!(k&1)) { k>>=1; int t=ksm(x,k,p); if(t!=1 && t!=p-1) return false; if(t==p-1) return true; } return true; } inline bool Miller_Rabin(int p) { if (p==1 || p==2152302898747) return false; for (int i=0;i<9;i++) if (p==pri[i]) return true; else if (p%pri[i]==0 || (!MR(pri[i],p))) return false; return true; } inline int Pollard_Rho(int n,int c) { int i=0,k=2,x=rand()%(n-1)+1,y=x; while(true) { i++; x=(x*x%n+c)%n; int d=gcd((y-x+n)%n,n); if(d!=1 && d!=n) return d; if(x==y) return n; if(i==k) y=x,k<<=1; } } inline void find(int x,int c) { if(x==1) return; if(Miller_Rabin(x)) { v.push_back(x); return; } int p=x; while(p>=x) p=Pollard_Rho(p,c--); find(p,c); find(x/p,c); } //MR,Miller_Rabin,Pollard_Rho,find函数是用来高效分解质因数的,存在一个vector中 //看不懂可以去看另一个代码,或者去P4718学习Pollard_Rho signed main(void) { read(n); find(n,200); sort(v.begin(),v.end()); for (i=0;i<v.size();i++) { j=i,cnt=1; while (i<v.size()-1 && v[j]==v[i+1]) //找相等质因数的个数 i++,cnt++; if (v[j]%4==1) //如果mod4=1,更新答案 ans*=(cnt*2+1); } print(ans*4); //输出 return 0; } ``` 正常分解是$\Theta(n^\frac{1}{2})$ $\mathbb{CODE:}$ ```cpp #include <bits/stdc++.h> #define int long long int n,i,cnt,ans=1; //ans初始赋为1,因为与坐标轴上有4个整点 inline void read(int &x) //快读 { short negative=1; x=0; char c=getchar(); while(c<'0' || c>'9') { if(c=='-') negative=-1; c=getchar(); } while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); x*=negative; } inline void print(int x) //快输 { if (x<0) putchar('-'),x=-x; if (x>9) print(x/10); putchar(x%10+'0'); } signed main(void) { read(n); for (i=2;i<=ceil(sqrt(n));i++) //因式分解,O(sqrt(n)) if (!(n%i)) { if (i%4==1) //如果i是个模4等于1的质数 { cnt=0; while (!(n%i)) cnt++,n/=i; //计算指数 ans*=(2*cnt+1); //更新答案 } while (!(n%i)) //把多余的除掉 n/=i; } if (n!=1 && n%4==1) //如果n是个模4等于1的质数 ans*=3; print(4*ans); //记得乘4 return 0; } ```