Solvution

求一个给定的圆(x^2+y^2=r^2),在圆周上有多少个点的坐标是整数。

Case #1

Case #2

看了这个视频后,就能想到另外的做法了,涉及到高斯整数、复平面等相关数学知识。
从视频中我们可以得到,给出如下的不定方程,可以得到的解的个数为
其中算术函数定义如下:

同时,我们有一个正整数以及他的唯一分解式
然后对于一个数我们就可以不考虑他为的质因子,那么就只剩下型质因子和型质因子,可以通过唯一分解定理得到因数总个数
可以分别算出型因数的个数或型因数的个数,从而得到另外一个的个数来算出最后的答案
这里考虑算型因数的个数,因为型的因数可以由任意个的质因子和偶数个的质因子相乘得到。
然后可以考虑dp,设为第型质因子,是否有多余因子的总方案数,那么就可以得到一个转移式:


然后就可以算出最后的答案了。

Code

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define LL long long
using namespace std;
const int N = 50000 + 5;
int pri[N] , cnt[N] , fac[N];
bool mark[N];
int n , tot , top;
LL sum , gasu , dp[N][2];
void prime(int n)
{
    sum = gasu = dp[0][0] = 1;
    rep(i , 2 , n)
    {
        if(!mark[i]) pri[++tot] = i;
        rep(j , 1 , tot)
        {
            if(i * pri[j] > N) break;
            mark[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}
int main()
{
    scanf("%d" , &n);
    while(n % 2 == 0) n >>= 1;
    prime(sqrt(n));
    rep(i , 1 , tot)
    {
        if(n % pri[i] == 0)
        {
            int k = 0;
            while(n % pri[i] == 0) n /= pri[i] , k++;
            k <<= 1;
            sum *= k + 1;
            if(pri[i] % 4 == 3) cnt[++top] = k , fac[top] = pri[i];
            else gasu *= (k + 1);
        }
    }
    if(n > 1)
    {
        sum *= 3;
        if(n % 4 == 3) cnt[++top] = 2 , fac[top] = n;
        else gasu *= 3;
    }
    rep(i , 1 , top)
    {
        dp[i][0] = dp[i-1][0] * (cnt[i] / 2 + 1) + dp[i-1][1] * (cnt[i] / 2);
        dp[i][1] = dp[i-1][0] * (cnt[i] / 2) + dp[i-1][1] * (cnt[i] / 2 + 1);
    }
    gasu *= dp[top][0];
    printf("%lld\n" , 4 * (2 * gasu - sum));
    return 0 ;
}

Case #3

对于刚才的算法实际上还有优化的余地,我们只需考虑型因子的贡献就可以算出最后的答案

Code

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int n , d , Ans = 4;
int main()
{
    scanf("%d",&n);
    while(n % 2 == 0) n >>= 1;
    d = sqrt(n);
    rep(i , 2 , d)
        if(n % i == 0)
        {
            int k = 0;
            while(n % i == 0) k += 2 , n /= i;
            if(i % 4 == 1) Ans *= k + 1;
        }
    if(n > 1 && n % 4 == 1) Ans *= 3;
    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注