HDU 3501-Calculation 2(欧拉函数)

题目链接:传送门

题意：求区间 [1,n-1] 内与n不互质的数的和。

欧拉函数性质： 区间 [1,n-1] 内与n互质的数的和为 phi(n)*n/2  用总和 n*(n-1)/2 (等差数列和) 减去 phi(n)*n/2 即为所求答案。

欧拉函数版：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 360
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
ll phi(ll n)
{
    ll ans=n,m=(ll)sqrt(n+0.5);
    for(ll 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()
{
    ll n;
    while(~scanf("%lld",&n)&&n)
    {
        if(n==1)
        {
            puts("0");
            continue;
        }
        ll sum=(n-1)*n/2;
        ll ans=phi(n)*n/2;
        printf("%lld\n",(sum-ans)%Mod);
    }
    return 0;
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define maxn 360
#define _ll __int64
#define ll long long
#define INF 0x3f3f3f3f
#define Mod 1000000007
#define pp pair<int,int>
#define ull unsigned long long
#define max(x,y) ( ((x) > (y)) ? (x) : (y) )
#define min(x,y) ( ((x) > (y)) ? (y) : (x) )
using namespace std;
ll fac[maxn],tot,ans;
void div(ll n)
{
    tot=0;
    ll m=(ll)sqrt(n+0.5);
    for(ll i=2;i<=m;i++)
    {
        if(n%i==0)
        {
            fac[tot++]=i;
            while(n%i==0)n/=i;
        }
    }
    if(n>1)fac[tot++]=n;
}
void dfs(ll num,ll s,ll r,ll n)
{
    if(num==tot)
    {
        if(s&1)ans-=n/r;
        else ans+=n/r;
        return ;
    }
    dfs(num+1,s,r,n);
    dfs(num+1,s+1,r*fac[num],n);
}
int main()
{
    ll n;
    while(~scanf("%lld",&n)&&n)
    {
        if(n==1)
        {
            puts("0");
            continue;
        }
        div(n);ans=0;dfs(0,0,1,n);
        ll sum=(n-1)*n/2;
        ll tem=ans*n/2;
        printf("%lld\n",(sum-tem)%Mod);
    }
    return 0;
}

HDU 3501-Calculation 2(欧拉函数)

原文：http://blog.csdn.net/qq_16255321/article/details/41645997