运用1：求小于或等于n并且和n互质的数的个数,记作φ(n)
通式：φ(x) = x(1-1/p1)(1-1/p2)(1-1/p3)...(1-1/pn)
其中p1，p2，p3...pn为x的质因数，每种质因数只有一个。
如12=2*2*3，φ(12)=12*(1-1/2)*(1-1/3)=4 (1,5,7,11)
如11=1*11，φ(11)=11*(1-1/11)=10 (1,2,3,4,5,6,7,8,9,10)
特例：φ(1)=1 (1)
模板函数
int oula(int n) { int sum=n;///如果n=1，直接返回1 for(int i=2;i*i<=n;i++) { if( n%i==0 ) sum = sum/i*(i-1);///先除后乘，防爆 while( n%i==0 )///比如12=2*2*3；所有2的倍数全部除完再走下一个质因数 n=n/i; } if(n>1) sum=sum/n*(n-1);///如果除后的n是质数，不符合i*i<=n return sum; }
运用2：求不大于n并且和n互质的所有正整数的和
通式： n*φ(n)/2
运用3：求不大于n并且和n不互质的所有正整数的和(总和减去互质的数的和)
通式：n*(n-1-φ(n))/2
#include<stdio.h> #include<algorithm> #include<iostream>using namespace std; #define ll long long ll oula(long long n) { long long sum=n,i,temp=n; for(i=2;i*i <=n;i++) { //欧拉公式 oula(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)...*(1-1/px) //p1,p2,p3为n的质因数 if(n%i==0) sum=sum/i*(i-1);//1.先除再乘防爆 2.公式里只要乘一次 while(n%i==0)//比如12=2*2*3；所有2的倍数全部除完再走下一个质因数 n=n/i; } if(n>1) sum=sum/n*(n-1);//到最后这个数是素数了 例如28=2*2*7； return sum; } int main(){ ll n,result; while(cin>>n&&n) {//大于n且与n互质的所有正整数的和为n*oula(n)/2 //结果=所有的和-互质的和 result=n*(n-1-oula(n))/2%1000000007; cout<<result<<endl; } return 0; }