HDU 3501 Calculation 2(容斥原理、求[1,n - 1]中和n不互素的数字之和)

题目链接；
HDU 3501 Calculation 2
题意：
求$[1,n - 1]$中和$n$不互素的数字之和。
数据范围：$1\leq n \leq 10^9$
分析：
和HDU 4135 Co_prime类似。我们只需求出不互素的数字的约数是由哪些$n$的素因子组成。
找到最小素因子组成。共有$n-1/mul$个数，最小的是$mul$且这些数是等差数列，用个求和公式，同样是奇加偶减，就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <vector>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const ll mod = (ll)(1e9) + 7;vector<ll> fac;void GetFactor(ll n)
{fac.clear();for(ll i = 2; i * i <= n; ++i) {if(n % i == 0) {fac.push_back(i);while(n % i == 0) n /= i;}}if(n > 1) fac.push_back(n);
}ll solve(ll A, ll n)
{ll ans = 0;int total = fac.size();for(ll i = 1; i < (1 << total); ++i) { //用二进制位表示该位上对应编号的素因子是否选择int bits = 0;ll res = 1;for(int j = 0; j < total; ++j) {if(i & (1 << j)) { //如果选择了第j个素因子bits++;res *= fac[j];}}ll t = A / res;if(bits & 1) ans += t * (t + 1) / 2 % mod * res; //选择的素因子个数为奇数个else ans -= t * (t + 1) / 2 % mod * res;ans %= mod;}return (ans + mod) % mod;
}int main()
{ll n;while(~scanf("%lld", &n) && n) {GetFactor(n);printf("%lld\n", solve(n - 1, n));}return 0;
}