@description@
设 S(n, m) 为满足 m mod k + n mod k >= k 的所有整数 k 组成的集合。求：
[phi(n) imes phi(m) imes sum_{kin S(n, m)}phi(k) mod 998244353
]
@solution@
对不起，我没学过数论.jpg。
两种方法。一种是猜想它有规律，打表发现原式为 (phi(n) imes phi(m) imes n imes m)。
另一种采用严谨推导。首先 mod 不好办，转成向下取整：
[m - lfloor frac{m}{k}
floor k + n - lfloor frac{n}{k}
floor k geq k\
lfloorfrac{n+m}{k}
floor - lfloor frac{m}{k}
floor - lfloor frac{n}{k}
floor geq 1
]
又因为显然有 (lfloorfrac{n+m}{k} floor - lfloor frac{m}{k} floor - lfloor frac{n}{k} floor = 0 或 1)，所以 (lfloorfrac{n+m}{k} floor - lfloor frac{m}{k} floor - lfloor frac{n}{k} floor = 1)。
代回去推导：
[sum_{kin S(n, m)}phi(k) = sum(lfloorfrac{n+m}{k}
floor - lfloor frac{m}{k}
floor - lfloor frac{n}{k}
floor)phi(k)\
= sumlfloorfrac{n+m}{k}
floorphi(k) - sumlfloorfrac{n}{k}
floorphi(k) - sumlfloorfrac{m}{k}
floorphi(k)
]
考虑 (sumlfloorfrac{n}{k} floorphi(k) = sum_{k=1}^{n}(phi * I)(k) = sum_{k=1}^{n}k = frac{n(n +1)}{2})（一个有关 (phi) 的经典狄利克雷卷积式）。
那么代回去直接得到结果为 (n imes m)，因此打表出来的结论正确。
@accepted code@
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MOD = 998244353;
typedef long long ll;
ll phi(ll n) {
ll ret = 1; int p = sqrt(n);
for(int i=2;i<=p;i++)
if( n % i == 0 ) {
ret *= (i - 1), n /= i;
while( n % i == 0 )
ret *= i, n /= i;
}
if( n != 1 ) ret *= (n - 1);
return ret;
}
int main() {
ll N, M; scanf("%lld%lld", &N, &M);
int A = 1LL * (phi(N) % MOD) * (phi(M) % MOD) % MOD;
int B = 1LL * (N % MOD) * (M % MOD) % MOD;
printf("%lld
", 1LL * A * B % MOD);
}
@details@
话说这个优美的式子，有啥组合/数论意义吗？