记录编号	466730	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[UVA 11426] [济南集训 2017] 求gcd之和	最终得分	100
用户昵称	真的菜	是否通过	通过
代码语言	C++	运行时间	3.187 s
提交时间	2017-10-29 16:11:51	内存使用	115.95 MiB

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 10;
const int mod = 998244353;
typedef long long ll;
int phi[maxn];
ll pre_phi[maxn];
bitset<maxn> vis;
vector<int> pri;
ll mmod(ll a)
{
    a %= mod;
    a += mod;
    return a % mod;
}
void pre_cal(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!vis[i])
            pri.push_back(i), vis[i] = 1, phi[i] = i - 1;
        for (int j = 0; j < pri.size(); ++j)
        {
            ll k = pri[j] * i;
            if (k > n) break;
            vis[k] = 1;
            if (i % pri[j] == 0)
            {
                phi[k] = phi[i] * pri[j];
                break;
            }
            phi[k] = phi[i] * (pri[j] - 1);
        }
    }
    for (int i = 1; i <= n; ++i)
        pre_phi[i] += (pre_phi[i - 1] + phi[i]) % mod, pre_phi[i] %= mod;
}
int main()
{
    freopen("hoip.in", "r", stdin);
    freopen("hoip.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    pre_cal(max(n, m) + 4);
    ll ans = 0;
    if (n > m) swap(n, m);
    for (int i = 1, lst = 0; i <= n; i = lst + 1)
    {
        lst = min(n / (n / i), m / (m / i));
        ans += 1ll * (n / i) * (m / i) * (pre_phi[lst] - pre_phi[i - 1]);
        mmod(ans);
    }
    cout << ans % mod << endl;
}