CSP-S 2020模拟训练题1-信友队T1 四平方和

题意简述

\(n\)是正整数，其四个最小的因子分别为\(d_1,d_2,d_3,d_4\)。

求对于所有的\(n \le m\)满足

\[d_1^2+d_2^2+d_3^2+d_4^2=n
\]

的\(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;

}

巴特西

CSP-S 2020模拟训练题1-信友队T1 四平方和

题意简述

分析

Code

最新文章

热门文章