I数学题(欧拉函数)

题面描述
最近&＃xff0c;华东交通大学ACM训练基地的老阿姨被一个数学问题困扰了很久&＃xff0c;她希望你能够帮她解决这个问题。
这个数学问题是这样的&＃xff0c;给你一个N,要求你计算
 

gcd(a,b)表示a和b的最大公约数

输入描述:

多组输入&＃xff0c;每行一个整数n(1<&＃61;n<&＃61;10^14)。

输出描述:

每行一个整数&＃xff0c;表示答案。由于答案会很大你要对1000000007取模。

示例1

输入

4
10

输出

6
35


说明

样例一&＃xff0c;2&＃43;4&＃61;6。
样例二&＃xff0c;2&＃43;4&＃43;5&＃43;6&＃43;8&＃43;10&＃61;35。

以下是官方题解:

该公式相当于求  小于等于n中所有与n不互质的数的和 
根据欧拉函数得知  小于或等于n的数中&＃xff0c;与n互质的数的数目为φ(n)

小于或等于n的数中&＃xff0c;与n互质的数的数总和为 n/2*φ(n)  (n>1)
答案就是   
1. 0  (n&＃61;1)
2  n*(n&＃43;1)/2 - φ(n) * n / 2  (n>1)

也可以找出素因子进行容斥

AC:

#include
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define fillchar(a, x) memset(a, x, sizeof(a))
#define huan printf("\n")
#define debug(a,b) cout<#define ffread(a) fastIO::read(a)
using namespace std;
typedef long long ll;
typedef pair pii;
const int maxn&＃61;5e5&＃43;10,inf&＃61;0x3f3f3f3f;
const ll mod&＃61;1000000007;ll euler(ll n) //返回euler(n)
{ll res&＃61;n,a&＃61;n;for(ll i&＃61;2; i*i<&＃61;a; i&＃43;&＃43;){if(a%i&＃61;&＃61;0){res&＃61;res/i*(i-1);while(a%i&＃61;&＃61;0)a/&＃61;i;}}if(a>1)res&＃61;res/a*(a-1);return res%mod;
}ll pow_mod(ll n,ll m)
{ll ans &＃61; 1;while(m > 0){if(m & 1)ans &＃61; (ans * n) % mod;m &＃61; m >> 1;n &＃61; (n * n) % mod;}return ans;
}int main()
{ll n;while(scanf("%lld",&n)!&＃61;EOF){if(n&＃61;&＃61;1){printf("0\n");continue;}ll inv2&＃61;pow_mod(2,mod-2);ll temp&＃61;((n%mod)*((n&＃43;1)%mod)%mod)*inv2%mod;ll ans&＃61;temp-(euler(n)*(n%mod)%mod*inv2)%mod;printf("%lld\n",(ans%mod&＃43;mod)%mod);}return 0;
}