May 27, 2019 由 小羊
题目链接:计蒜客
对于给定的 ,我们要计算
首先,我们可以把乘积扔到指数上,变成求和;然后由于 是素数,我们求其指数模 。
考虑先对 求和,则此式可以变成
考虑这样的一个函数,并使用莫比乌斯反演、适当的求和变换和狄利克雷卷积的结论
回到原式,再使用求和变换
如果后面那个 可以用杜教筛计算出来,那么再预处理部分前缀和,我们就能 计算出结果啦!
既然杜教筛要配一个函数使得其狄利克雷卷积好计算,那么…我们好像只能配上 了。
好吧这个式子好像不太好求前缀和?不过考虑一下 求前缀和的方法,我们好像还是可以求的。
行吧,三个数论分块,写吧…馍馍片。
#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
const size_t MAXN = 1e6+5;
bool isnp[MAXN];
int pcn, pri[MAXN];
lld g[MAXN], q[MAXN], s[MAXN];
lld _P1[MAXN];
map<lld,lld> _P2;
int mod;
void init_prime()
{
_P1[1] = g[1] = q[1] = 1;
for (int i = 2; i < MAXN; i++)
{
if (!isnp[i])
{
g[i] = s[i] = 2*i-1;
q[i] = i-1;
pri[pcn++] = i;
}
for (int j = 0; j < pcn; j++)
{
int k = i * pri[j];
if (k >= MAXN) break;
isnp[k] = true;
if (i % pri[j] == 0)
{
s[k] = (s[i] + q[i] + 0ll) * pri[j];
q[k] = q[i] * pri[j];
g[k] = g[i] / s[i] * s[k];
break;
}
else
{
q[k] = q[pri[j]];
s[k] = s[pri[j]];
g[k] = g[i] * s[k];
}
}
_P1[i] = _P1[i-1] + g[i];
}
}
inline lld sumn(lld n)
{
return n*(n+1)/2%mod;
}
lld sum_xdx(lld n)
{
lld ans = 0;
for (lld l = 1, r; l <= n; l = r+1)
{
r = n / (n / l);
(ans += (sumn(r) - sumn(l-1)) * sumn(n/l) % mod) %= mod;
}
return ans;
}
lld G(lld n)
{
if (n < MAXN) return _P1[n] % mod;
else if (_P2.count(n)) return _P2[n];
lld ans = sum_xdx(n);
for (lld k = 2, fk; k <= n; k = fk+1)
{
fk = n / (n/k);
ans -= (fk-k+1) * G(n/k) % mod;
}
ans = (ans % mod + mod) % mod;
return _P2[n] = ans;
}
lld fpow(lld b, lld n, lld MOD)
{
lld a = 1;
while (n)
{
if (n & 1) a = a * b % MOD;
b = b * b % MOD;
n >>= 1;
}
return a;
}
inline lld sumn2(lld n)
{
__int128 s = n*2+1;
s *= n * (n+1);
s /= 6;
return lld(s % mod);
}
int main()
{
lld n, m, p;
scanf("%lld %lld %lld", &n, &m, &p);
mod = p-1;
init_prime();
G(n);
lld fff = 0;
for (lld l = 1, r; l <= n; l = r+1)
{
r = n / (n / l);
(fff += (G(r) - G(l-1)) * ((n/l) * (n/l) % mod)) %= mod;
}
if (fff < 0) fff += mod;
printf("%lld\n", fpow(m, fff, p));
return 0;
}
上面式子中,为了求某函数前缀和,写了一堆数组,在这里解释一下:
首先考虑 ,则有
于是不停的利用最小因子和它的积性去线性筛就好啦~
g[n]
表示 q[n]
表示 最小因子 以及其对应指数 所对应的 s[n]
表示 最小因子 以及其对应指数 所对应的 好麻烦啊QAQ