昨天看了的推导感觉很神！

今天想写结果又忘了怎么推的啦。。。233

 

1 /************************************************************** 2     Problem: 2154 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:5124 ms 7     Memory:127760 kb 8 ****************************************************************/ 9  10 #include 
      
       11 #include 
       
        12  13 using namespace std;14 typedef long long ll;15  16 const int N = 1e7 + 5;17 const ll mod = 20101009;18  19 int n, m;20 int p[N], cnt;21 bool vis[N];22 ll g[N];23  24 void get_g(int N) {25   int i, j, k;26   g[1] = 1;27   for (i = 2; i <= N; ++i) {28     if (!vis[i]) p[++cnt] = i, g[i] = 1 - i;29     for (j = 1; j <= cnt; ++j) {30       if ((k = i * p[j]) > N) break;31       vis[k] = 1;32       if (i % p[j] == 0) {33     g[k] = g[i];34     break;35       }36       g[k] = g[i] * (1 - p[j]);37     }38   }39   for (i = 2; i <= N; ++i) g[i] *= i;40   for (i = 1; i <= N; ++i)41     (g[i] += g[i - 1]) %= mod;42 }43  44 ll calc(int n, int m) {45   int i, j;46   ll t1, t2, res = 0;47   for (i = 1, j = 0; i <= n; i = j + 1) {48     j = min(n / (n / i), m / (m / i));49     t1 = (1ll * (n / i) * (n / i + 1) / 2) % mod;50     t2 = (1ll * (m / i) * (m / i + 1) / 2) % mod;51     (res += ((g[j] - g[i - 1]) * ((t1 * t2) % mod)) % mod) %= mod;52   }53   return (res % mod + mod) % mod;54 }55  56 int main() {57   int i, T;58   scanf("%d%d", &n, &m);59   if (n > m) swap(n, m);60   get_g(m);61   printf("%lld\n", calc(n, m));62   return 0;63 }