集合统计 / 简单的数学题 / 数学

题目链接：ybt金牌导航8-4-7 / SSL 2639 / bzoj 4173

题目大意

给你 n,m 要你求 φ(n)φ(m)sum φ(ai)。
其中 ai 是满足 n%x+m%x>=x 的所有 x。

思路

重新写式子：
设集合 \(S(n,m)\) 为满足 \(n\%k+m\%k\geqslant k\) 的 \(k\) 组成的集合。

然后要你求：\(\varphi(n)\varphi(m)\sum\limits_{k\in S(n,m)}\varphi(k)\)

其实你看样例啊什么都都可以猜出来，最右边这个是 \(n*m\)。

这里给一下证明：
\(k\left\lfloor\frac{n}{k}\right\rfloor+n\%k=n\)
\(k\left\lfloor\frac{m}{k}\right\rfloor+m\%k=m\)
两个加起来：
\(k\left\lfloor\frac{n}{k}\right\rfloor+n\%k+k\left\lfloor\frac{m}{k}\right\rfloor+m\%k=n+m\)
\((k\left\lfloor\frac{n}{k}\right\rfloor+k\left\lfloor\frac{m}{k}\right\rfloor)+(n\%k+m\%k)=n+m\)
然后根据 \(n\%k+m\%k\geqslant k\) 代替进去：
\(k(\left\lfloor\frac{n}{k}\right\rfloor+\left\lfloor\frac{m}{k}\right\rfloor)+k\leqslant n+m\)

然后显然 \(n\%k+m\%k\leq 2k\)，所以它除 \(k\) 向下取整是 \(1\)。
那我们就全部除 \(k\) 向下取整，那它前面 \(\geqslant\) 就肯定是 \(=\) 了。
\(\left\lfloor\frac{n}{k}\right\rfloor+\left\lfloor\frac{m}{k}\right\rfloor+1= \left\lfloor \frac{n+m} {k}\right\rfloor\)
\(\left\lfloor \frac{n+m}{k}\right\rfloor-\left\lfloor\frac{n}{k}\right\rfloor-\left\lfloor\frac{m}{k}\right\rfloor=1\)

然后我们带进去：
\(\sum\limits_{k\in S(n,m)}\varphi(k)\)
\(\sum\limits_{k=1}^{n+m}\varphi(k)*\left\lfloor \frac{n+m}{k}\right\rfloor-\sum\limits_{k=1}^{n}\varphi(k)\left\lfloor\frac{n}{k}\right\rfloor-\sum\limits_{k=1}^{m}\varphi(k)\left\lfloor\frac{m}{k}\right\rfloor\)

这里我看了半天才知道为什么，就是因为你上面这个式子：\(\left\lfloor \frac{n+m}{k}\right\rfloor-\left\lfloor\frac{n}{k}\right\rfloor-\left\lfloor\frac{m}{k}\right\rfloor\)
它肯定是 \(0/1\)，那不符合的情况就是 \(0\)，那就无影响也可以加上，然后右边两个因为大了之后除向下取整的结果肯定是 \(0\) 所以可以都不要。

然后你考虑 \(\sum\limits_{i=1}^x\varphi(i)\left\lfloor\frac{x}{i}\right\rfloor\) 怎么求。
\(\sum\limits_{i=1}^n\varphi(i)\left\lfloor\frac{n}{i}\right\rfloor=\sum\limits_{j=1}^n\sum\limits_{i|j}\varphi(i)=\sum\limits_{j=1}^nj\)

然后就成了：
\(\sum\limits_{k=1}^{n+m}k-\sum\limits_{k=1}^{n}k-\sum\limits_{k=1}^{m}k\)

然后三个等差序列和你化简一下就成了 \(n*m\)。

代码

#include
#define ll long long
#define mo 998244353

using namespace std;

ll n, m, pr[4000001];
ll ans;
bool np[40000001];

ll phi(ll now) {
    ll re = 1;
    for (int i = 1; i <= pr[0] && pr[i] * pr[i] <= now; i++) {
        if (now % pr[i] == 0) {
            re = re * (pr[i] - 1) % mo;
            now /= pr[i];
            while (now % pr[i] == 0) {
                re = re * pr[i] % mo; now /= pr[i];
            }
        }
    }
    if (now > 1) {
        re = re * (now - 1) % mo;
    }
    return re;
}

int main() {
    for (int i = 2; i <= 4e7; i++) {
        if (!np[i]) pr[++pr[0]] = i;
        for (int j = 1; j <= pr[0] && i * pr[j] <= 4e7; j++) {
            np[i * pr[j]] = 1; if (i % pr[j] == 0) break;
        }
    }
    
    scanf("%lld %lld", &n, &m);
    
    ans = (n % mo) * (m % mo) % mo;//直接上结论
    printf("%lld", ans * phi(n) % mo * phi(m) % mo);
    
    return 0;
}