BZOJ 3512: DZY Loves Math IV

### Description
给定n,m，求 模10^9+7的值。
### Input
仅一行，两个整数n,m。
### Output
仅一行答案。
### Sample Input
100000 1000000000

### Sample Output
857275582

数据规模：

$1<=n<=10^5，1<=m<=10^9$，本题共4组数据。

一道脑洞神题，$orz$出题人。
首先科普关于$\varphi$的小知识：
$$\varphi(xy)=\varphi(x)\varphi(\frac{y}{d})d$$
另一个版本是：
$$\varphi(xy)=\frac{\varphi(x)\varphi(y)d}{\varphi(d)}$$

这个很好理解，第一个相当于把质因数的交集去掉后并起来再补上。第二个相当于把质因数交集先补上，交起来的地方有两个$p-1$，再去除一个$\varphi(d)$补一个$d$。

现在我们回到这道题。
发现$n$是$10^5$，只要我们能快速算出下面的式子，那么就可以枚举$i$了：
$$f(x)=\sum^{x}_{j=1}\varphi(xj)$$

然后是一段脑洞大开的推导：
考虑这样一件事情，我们重新审视一下整数。
我们把整数看成质因数构成的多重集，
然后我们把$x$的每一种质因数拿一个出来，这样形成一个数，我们设为$u$，其余的部分也形成一个数，设为$r$，

那么
$$f(x)=r\sum^{x}_{j=1}\varphi(uj)$$
$$r\sum^{x}_{j=1}\varphi(j)\varphi(\frac{u}{d})d,\ d=gcd(u,j)$$

发现推不动了，这时候需要一点奇思妙想
$$r\sum^{x}_{j=1}\varphi(j)\varphi(\frac{u}{d})\sum_{k|d}\varphi(\frac{d}{k})$$

考虑后面的$\varphi$可以直接合起来，因为$u,d,k$都只有一层，也就是是一个不重集，那么显然就有

$$r\sum^{x}_{j=1}\varphi(j)\sum_{k|d}\varphi(\frac{u}{k})$$

这下就豁然开朗了

$$r\sum_{k|u}\varphi(\frac{u}{k})\sum^{\frac{x}{k}}_{j=1}\varphi(jk)$$

发现后面的变成了原问题，$\lfloor\frac{x}{k} \rfloor$只有$\sqrt n$种，暴力枚举约数就可以类似杜教筛的递归了
$k=1$返回$\varphi$的前缀和即可

```
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
 
const int B = 5e6, mod = 1e9 + 7;
int Sphi[B + 5], vis[B + 5], phi[B + 5];
int U[B + 5], pri[B + 5], n, m;
map<int, int > hsh;
typedef pair<int, int > pii;
map<pii, int > phsh;
 
inline void Add(int &x, const int &a) {
    x += a; if(x >= mod) x -= mod;
}
inline void Dec(int &x, const int &a) {
    x -= a; if(x < 0) x += mod;
}
inline void mul(int &x, const int &a) {
    x = 1ll * x * a % mod;
}
 
void pre() {
    U[1] = vis[1] = 1, Sphi[1] = phi[1] = 1;
    for(register int i = 2; i <= B; ++i) {
        if(!vis[i]) U[i] = i, phi[i] = i - 1, pri[++(*pri)] = i;
        for(register int j = 1; i * pri[j] <= B && j <= *pri; ++j) {
            vis[i * pri[j]] = 1;
            U[i * pri[j]] = U[i] * pri[j];
            phi[i * pri[j]] = phi[i] * (pri[j] - 1);
            if(i % pri[j] == 0) {
                phi[i * pri[j]] = phi[i] * pri[j];
                U[i * pri[j]] = U[i];
                break;
            }
        }
    }
    for(register int i = 1; i <= B; ++i)
        Sphi[i] = Sphi[i - 1], Add(Sphi[i], phi[i]);
}
 
int GetSphi(int n) {
    if(n <= B) return Sphi[n];
    if(hsh[n]) return hsh[n];
    int sum = (1ll * (n + 1) * n / 2) % mod;
    for(register int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        Dec(sum, (1ll * GetSphi(n / r) * (r - l + 1)) % mod);
    }
    return hsh[n] = sum;
}
 
int GetAns(int n, int a) {
    int sum = 0;
    if(a == 1) return GetSphi(n);
    if(n == 0) return 0;
    if(phsh[make_pair(n, a)]) 
        return phsh[make_pair(n, a)];
    for(register int k = 1; k * k <= a; ++k) {
        if(a % k != 0) continue;
        Add(sum, 1ll * phi[a / k] * GetAns(n / k, k) % mod);
        if(k * k != a) {
            Add(sum, 1ll * phi[k] * GetAns(n / (a / k), a / k) % mod);
        }
    }
    return phsh[make_pair(n, a)] = sum;
}
 
int ans[100005], sum;
int main() {
    scanf("%d%d", &n, &m);
    pre();
    for(register int i = 1; i <= n; ++i) {
        if(U[i] == i) ans[i] = GetAns(m, i);
        else ans[i] = 1ll * ans[U[i]] * (i / U[i]) % mod;
        Add(sum, ans[i]);
    }
    printf("%d", sum);
    //printf("%d", GetAns(n, m));
    return 0;
} 
```

Rockdu's Blog

导航

最近发表

大佬们的友链