题解 P5560 【[Celeste-B]Golden Feather】

· · 题解

一个初一生试着给出一篇数学证明

\color{grey}\text{这里只是简单的说一个大概思路}

首先我们设 f(n)=(n+1)^2-1

易知 f(n)=n(n+2)

对于 gcd \left(\ f(n),f(n-1) \right.)= gcd\left(\ n(n+2),(n+1)(n+3) \right. )

其中 n 与 (n+1) , (n+2) 与 (n+3) , (n+2) 与 (n+1) 都是互质的

\therefore$ $gcd \left( f(n),f(n-1) \right.)$ 当且仅当 $n \equiv 1 \ (mod 3)$ 时有公因数 $3 #### 现在我们来讨论 $n \equiv 1 \ (mod 3)$ 时的情况 在满足大前提的情况下 #### 1： 当 $n$ 为奇数时，将 $f(n)$ 与 $f(2)$ 连接就好了 #### 2： 当 $n$ 为偶数时，试验一下 , $f(4)$ 与 $f(10)$ 在其前面无与它互质的 而$f(4)$ 与 $f(5)$ 是互质的，$f(10)$ 与 $f(11)$ 是互质的 $\therefore$对于 $f(4)$ 与 $f(10)$ 要特判 ( 它们可以与 $f(1)$ 连，此时其他连接是 $1$ , 这个是 $3$ , 所以一共是 $5$ 或 $10$ ) $f(16)$ 与 $f(11)$ 互质。 $f(22)$ 与 $f(17)$ 互质。 ... #### ~~对于任意一个$f(n)$ , 你可以去跑一跑试试(逃~~ #### 2\#: 现在我们定义一个数列 $n_i$ 满足 $n_i \equiv 4 (mod 6)

易知 f(n_i) 就是我们讨论的

如果孪生素数猜想是成立的

那么取 a 使 a 与 a+2 都是素数，

那么若 f(a) 与 f(n) 不互质，则 f(n) \equiv 0 (mod\ \ a/a+2)

多取几组就知道 f(n) 远远应大于其本身，于是矛盾（此处证明仍有缺陷）

初一生只能做到这一步了

先上 AC 代码吧：

code：

#include<bits/stdc++.h>
using namespace std;
long long n,T;
int main(){
    cin>>T;
    for(int i=1;i<=T;i++){
        cin>>n;
        if(n==4||n==10)cout<<n+1<<endl;
        else cout<<n-1<<endl;
    }
    return 0;
}