CSP-S 2020模擬訓練題1-信友隊T1 四平方和

• 2020 年 11 月 4 日
• 筆記
• 數論----difficult, 數論----同餘

題意簡述

\(n\)是正整數，其四個最小的因子分別為\(d_1,d_2,d_3,d_4\)。

求對於所有的\(n \le m\)滿足

的\(n\)的個數。

分析

這是一道數競題，下面來求\(n\)。

顯然\(d_1=1\)，則\(n=1+d_2^2+d_3^2+d_4^2\)。

若\(n\)是奇數，則其因子都是奇數，其平方和為四個奇數相加為偶數，矛盾。故n為偶數，\(d_2=2\)，則\(n-5=d_3^2+d_4^2\)。

此時，\(d_3\)只可能是\(3,4\)或者大於\(4\)的質數

• 若\(d_3=3\)，則\(d_4=4\)或\(d_4=6\)，驗算得不存在這樣的\(n\)
• 若\(d_3=4\)，則由奇偶性可得，\(d_4\)一定為奇數，所以\(d_4^2 \equiv 1(\mbox{mod } 4)\)，但\(n-5-d_3^2=n-21 \equiv 3(\mbox{mod }4)\)，所以矛盾。

所以\(n\)只能是一個大於\(4\)的質數，且\(d_4=2d_3\)，故\(n-5=5d_3^2 \Longrightarrow n=5(d_3^2+1)\)。故\(5 \nmid n\)，即\(d_3=5,d_4=10\)，得\(n=130\)。故\(\forall n \in \mathbb{N^+}\)只有\(n=130\)符合題意。

Code

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#define IL inline
#define re register
#define LL long long
#define ULL unsigned long long
#define re register
#define debug printf("Now is %d\n",__LINE__);
using namespace std;

template<class T>inline void read(T&x)
{
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    x=ch-'0';ch=getchar();
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
}
inline LL read()
{
	int x=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    x=ch-'0';ch=getchar();
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int G[55];
template<class T>inline void write(T x)
{
    int g=0;
    if(x<0) x=-x,putchar('-');
    do{G[++g]=x%10;x/=10;}while(x);
    for(re int i=g;i>=1;--i)putchar('0'+G[i]);putchar('\n');
}
LL n;
int main()
{
	n=read();
	if(n>=130) cout<<1<<endl;
	else cout<<0<<endl;
	return 0;
}