2020cug新生赛 An easy problem

An easy problem

为2020cug新生赛出的一个题目，出题想法来自信息安全概论课后习题，稍微改复杂了一点。

题目:

给定一个正整数(n(n<10000000))。求满足条件的非负整数(a,b,c(a<n,b<n,c<n,a+b<n))，使得对于任意的正整数(x),(0<=x<n,F(x))形成一对一的映射关系,即对于任意(x_i ot=x_j)，都有(F(x_i) ot=F(x_j))。其中,(F(x)={((a+b)*x+c)}mod n)。
求有多少对满足条件的不同的三元组(a,b,c)，对(10^9+7)取模。

输入：

输入文件包含多组数据(不超过60组数据)，请处理到文件结束。
每组数据为1个正整数(n(n<10000000))。

输出：

对于每组数据输一行，包括一个整数,表示满足条件的三元组(a,b,c)个数取模的结果。

Sample Input

1000000

Sample Output

599997214

题解:

(F(x)=((a+b)*x+c)mod n)
题目要求 (F(x)) 形成一一映射，由x的数量知，(F(x))的值必定分布为{0，1，...,n-1}，所以形成的是一个关于n的完全剩余系，不了解完全剩余系性质也完全没有问题。
易知：
1.(c) 只是对结果的一个偏移，不决定是否形成一一映射，所以c取值为n种，接下来只考虑 (F(x)=(a+b)*xmod n)
2. 现在不考虑n为1的情况，令 (m=(a+b)),(m<n) 。对于任意(x_i>x_j),都有：$$F(x_i)-F(x_j) e0$$ 即 $$m(x_i-x_j)mod n e0$$由于(x_i-x_j)可以取到[1,n) 任意值，所以容易得到m必须与n互质才能保证上面的等式。所以m的取值个数就是n的欧拉函数 (phi(n))。
3. 考虑二元组 (a,b) 的取值个数，就是与 (n) 互质的全部数之和 (这个结果推导较为简单，可以自行百度) + (phi(n))。
最终满足条件的三元组个数为：

[(phi(n)+ sum_{gcd(i,n)=1}^ni)*n ]

即

[(phi(n)+ n*phi(n)/2)*n ]

注意输出时中间结果先mod一下,以免爆long long。此公式同时满足n=1的答案，所以无需特判。
(如有不足，欢迎指出！)

代码:

#include <iostream>
#include <algorithm>
#include<cmath>
#define ll long long
using namespace std;
const int mod=1e9+7;
int eulur_phi(int n)
{
    int m = (int)sqrt(n+0.5);
    int ans = n;
    for(int i=2;i<=m;i++)
        if(n%i == 0)
    {
        ans = ans/i*(i-1);
        while(n%i == 0)n/=i;
    }
    if(n>1)ans = ans/n*(n-1);
    return ans;
}
int main(){
    int n;
    while(cin>>n){
    ll a = eulur_phi(n);
    ll ans = ((a*n/2+a)%mod*n)%mod;
    cout<<ans<<endl;
    }
}