题解 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:} 
#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:} 
#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;
}