BZOJ3512 DZY Loves Math IV

3512: DZY Loves Math IV

Time Limit: 15 Sec Memory Limit: 128 MB

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组数据。

数论神题系列，成功卡了3天。。。

首先n很小，直接枚举

然后根据[ varphi(in) = varphi(i) cdot varphi(frac{n}{d})cdot sum_{emid d} varphi(e) = varphi(i) cdot sum_{emid d}varphi(frac{n}{e}) ]这个式子

可以推得[ S(n,m) = sum_{dmid n}varphi(frac{n}{d})cdot S(d, lfloor frac{m}{d} floor) ]

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 template <class _T> inline void read(_T &_x) {
  4     int _t; bool flag = false;
  5     while ((_t = getchar()) != '-' && (_t < '0' || _t > '9')) ;
  6     if (_t == '-') _t = getchar(), flag = true; _x = _t - '0';
  7     while ((_t = getchar()) >= '0' && _t <= '9') _x = _x * 10 + _t - '0';
  8     if (flag) _x = -_x;
  9 }
 10 using namespace std;
 11 const int mod = 1e9 + 7;
 12 const int N = 1e5 + 10;
 13 const int M = 7e6 + 10;
 14 typedef long long LL;
 15 inline int add(int a, int b) {
 16     a += b;
 17     if (a < 0) a += mod; if (a >= mod) a -= mod;
 18     return a;
 19 }
 20 inline int mul(int a, int b) {
 21     return (int)((LL)a * b % mod);
 22 }
 23 int phi[M], prime[M / 10], pcnt;
 24 int Div[N], mx[N];
 25 bool vis[M];
 26 inline void init() {
 27     phi[1] = mx[1] = Div[1] = 1;
 28     for (register int i = 2, j, tmp; i < M; ++i) {
 29         if (!vis[i]) {
 30             prime[++pcnt] = i;
 31             phi[i] = i - 1;
 32             if (i < N) Div[i] = 1, mx[i] = i;
 33         }
 34         for (j = 1; j <= pcnt && (LL)prime[j] * i < M; ++j) {
 35             tmp = prime[j] * i;
 36             vis[tmp] = true;
 37             if (tmp < N) mx[tmp] = prime[j];
 38             if (i % prime[j] == 0) {
 39                 phi[tmp] = phi[i] * prime[j];
 40                 if (tmp < N) Div[tmp] = Div[i] * prime[j];
 41                 break;
 42             }
 43             phi[tmp] = phi[i] * (prime[j] - 1);
 44             if (tmp < N) Div[tmp] = Div[i];
 45         }
 46     }
 47     for (register int i = 2; i < M; ++i) phi[i] = add(phi[i], phi[i - 1]);
 48 }
 49 struct Hash_table {
 50     int tot, fir[10000];
 51     struct Edge {
 52         int v, res, nxt;
 53     }e[100000];
 54     Hash_table() {memset(fir, -1, sizeof fir); tot = 0; }
 55     inline void add(int a, int b, int c) {
 56         e[++tot] = (Edge){b, c, fir[a]};
 57         fir[a] = tot;
 58     }
 59     inline int find(int x) {
 60         int w = x >> 20;
 61         for (int u = fir[w]; ~u; u = e[u].nxt)
 62             if (e[u].v == x) return e[u].res;
 63         return -1;
 64     }
 65     inline void insert(int v, int res) {
 66         add(v >> 20, v, res);
 67     }
 68 }mp;
 69 int Phi(int n) {
 70     if (n < M) return phi[n];
 71     int w = mp.find(n); if (~w) return w;
 72     int res = (int)(((LL)n * (n + 1) >> 1) % mod);
 73     for (int i = 2, j; i <= n; i = j + 1) {
 74         j = n / (n / i);
 75         res = add(res, -mul(j - i + 1, Phi(n / i)));
 76     }
 77     mp.insert(n, res); return res;
 78 }
 79 int sum(int n, int m) {
 80     if (!m) return 0;
 81     if (m == 1) return phi[n] - phi[n - 1];
 82     if (n == 1) return Phi(m);
 83     int &k = mx[n];
 84     return add(mul(sum(n / k, m), k - 1), sum(n, m / k));
 85 }
 86 int f[100010];
 87 int main() {
 88     //freopen("3512.in", "r", stdin);
 89     //freopen("3512.out", "w", stdout);
 90     init();
 91     int n, m, ans = 0; read(n), read(m);
 92     memset(f, -1, sizeof f);
 93     for (int i = 1; i <= n; ++i) {
 94         int k = Div[i], t = i / k, ret;
 95         if (~f[t]) ret = mul(k, f[t]);
 96         else ret = mul(k, (f[t] = sum(t, m)));
 97         ans = add(ans, ret);
 98     }
 99     cout << ans << endl;
100     return 0;
101 }

View Code