題意:給出n(1<=n<=10^8),求小于n的,求所有與n互質的數字的四次幂的加和是多少。
分析:容斥原理
首先要知道四次幂求和公式,1^4+2^4+...+n^4=n*(n+1)*(2n+1)*(3n^2+3n-1)/30
先求所有小于等于n的數字的四次幂和,然後減去那些不互質的即可。
這個減去的過程用到了容斥原理。
先對n分解質因子,每個不同的質因子隻保留一個。
然後分别枚舉這些質因子的組合情況,由奇數個因子組成的數要減去,由偶數個因子組成的數要加上。
對于一個因子組合的乘積a,我們需要一次性計算a^4+(2a)^4 + (3a)^4+...
将其轉化為a^4 * (1^4+2^4+...)即可。
這道題還有一個難點,就是公式中有除法(除以30),卻還要進行模運算。
除法是不支援模運算的,是以我們要将除法轉化為乘法,除以30變為乘以30的逆元。
逆元的意思是,如果a、b互為mod c下的逆元,則a * b = 1 (mod c)。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-YWan5yMmZjM4EmM5EWN4MWNiZ2NjFzNjhzNkFmZ4kTN1ADN08CX1AzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLzM3Lc9CX6MHc0RHaiojIsJye.gif)
#include <cstdio>
using namespace std;
#define D(x)
const int MOD = (int)(1e9) + 7;
const int MAX_FACTOR = 40;
int n;
int factor_num;
long long factor[MAX_FACTOR];
long long inverse;
//n(n+1)(2n+1)(3n^2+3n-1)/30
long long to_forth(long long value)
{
long long ret = value;
ret = ret * ret % MOD;
ret = ret * ret % MOD;
return ret;
}
long long cal(long long value)
{
long long num = n / value;
long long ret = 1;
ret = ret * num % MOD * (num + 1) % MOD;
ret = ret * (2 * num + 1) % MOD;
ret = ret * ((num * num % MOD * 3 % MOD + 3 * num % MOD - 1) % MOD) % MOD;
if (ret / 30 != ret * inverse % MOD)
{
D(printf("#%lld %lld\n", ret / 30, ret * inverse % MOD));
}else
{
D(printf("**\n"));
}
ret = ret * inverse % MOD;
ret = ret * to_forth(value) % MOD;
return ret;
}
void get_factors()
{
factor_num = 0;
int m = n;
for (int i = 2; i * i <= m; i++)
{
if (m % i == 0)
factor[factor_num++] = i;
while (m % i == 0)
{
m /= i;
}
}
if (m != 1)
{
factor[factor_num++] = m;
}
}
long long work()
{
long long ans = 0;
for (int i = 1; i < (1 << factor_num); i++)
{
int num = 0;
long long temp = 1;
int index = 0;
for (int mask = 1; mask <= i; mask <<= 1, index++)
{
if ((mask & i) == 0)
{
continue;
}
num++;
temp *= factor[index];
}
D(printf("temp=%lld\n", temp));
if (num & 1)
ans += cal(temp);
else
ans -= cal(temp);
ans = (ans % MOD + MOD) % MOD;
}
ans = ((cal(1) - ans) % MOD + MOD) % MOD;
return ans;
}
void gcd_extend(long long a,long long b,long long &g,long long &x,long long &y)
{
if (!b)
{
g = a;
x = 1;
y = 0;
return;
}
gcd_extend(b, a % b, g, y, x);
y -= a / b * x;
}
int main()
{
long long x, y, g;
gcd_extend(30, MOD, g, x, y);
D(printf("%lld %lld %lld\n", x, y, g));
x = (x % MOD + MOD) % MOD;
inverse = x / g;
D(printf("%lld\n", inverse));
D(printf("%lld\n", inverse * 30 % MOD));
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
if (n == 1)
{
puts("0");
continue;
}
get_factors();
int ans_int = work();
printf("%d\n", ans_int);
}
return 0;
}
View Code