C - Calculation 2 HDU - 3501 （欧拉）

Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.

InputFor each test case, there is a line containing a positive integer N(1 ≤ N ≤ 1000000000). A line containing a single 0 follows the last test case.OutputFor each test case, you should print the sum module 1000000007 in a line.Sample Input

Sample Output

0

2

给定一个正整数N，你的任务是计算小于N的正整数的和，这些正整数不是共圆到N的。

输入

对于每个测试用例，有一行包含一个正整数N(1≤N≤1000000000)。最后一个测试用例后面有一行包含一个0。

输出

对于每个测试用例，您应该在一行中打印sum模块1000000007。

样例输入

样例输出

思路：本来以为这道题会是欧拉函数只不过返回的不是欧拉数，而是GCD(n,i)大于一的和，结果WA了

想了想，以6为例

1 2 3 4 5 6 其中 2 3 4 都是满足题意的，但是欧拉函数不会走4，他只会走它所有的质因子

没有办法，只有看大佬题解，借鉴后看到了求互质的数字和可以直接利用 n * enler( n) / 2求解，而此题要求的是非互质的，同样可以使用这个性质

于是就一个欧拉函数，轻松AK,看到大佬用容斥写，哎还是见识太短，学的太少，小菜鸟今天又是队伍倒一。。。。。。。。

#include <iostream>

#include <cstdio>

#include <string>

#include <algorithm>

#include <map>

#define Mod 1000000007

using namespace std;

typedef long long ll;

const  ll N = +;

int elh[N];

int a;

ll Euler(ll n)

{

    ll res =n;

    for(int i=;i<=n/i;i++)

    {

        if(n%i==)

        {

            res = res-res/i;

        }

        while(n%i==)n/=i;

    }

    if(n>)res =res- res/n;

    return res%Mod;

}

int main()

{

    while(~scanf("%lld",&a)&&a)

    {

        cout <<(a*(a--Euler(a))/)%Mod<<endl;

    }

    return ;

}

巴特西

C - Calculation 2 HDU - 3501 （欧拉）

最新文章

热门文章