【数学|数学题---与n互质数字之和】给出一个n，求1…n中与n互质的数的和
公式为
r e s = n ? p h i ( n ) / 2 res = n*phi(n)/2 res=n?phi(n)/2
phi为欧拉函数
#include
#include
#include
#include
#include
using namespace std;
#define int long long
const int mod = 1000000007;
int qmi(int a,int b){int res=1;
while(b){if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}return res%mod;
}
int phi(int x){
int res=x;
for(int i=2;
i<=x/i;
i++){
if(x%i==0){
res=res/i*(i-1);
while(x%i==0)x/=i;
}
}
if(x>1)res=res/x*(x-1);
return res%mod;
}int Mod(int x)
{
return ((x%mod)+mod)%mod;
}signed main()
{
int n;
while(cin>>n)
{
int s=Mod(Mod(n)*Mod(n+1));
s=Mod(s*qmi(2,mod-2));
int t=Mod(Mod(n)*Mod(phi(n)));
t=Mod(t*qmi(2,mod-2));
cout< 推荐阅读
- 图论|判断图连通性的三种方法（并查集/dfs/bfs）
- CSC148H1 算法比较分析
- 因果推断在哈啰出行的实践探索
- leecode题解|「代码随想录」968.监控二叉树【贪心算法】力扣详解！
- C语言与C++编程|二叉树操作详解
- 链表|关于链表的经典OJ题
- 算法|不会有人2022年还不懂栈吧（）
- 算法|【算法】【C语言进阶】C语言字符串操作宝藏级别汇总 strtok函数 strstr函数该怎么用（【超详细的使用解释和模拟实现】）
- 人工智能|PPF（Point Pair Features）原理及实战技巧