[HDU 5780]gcd

danihao123 posted @ 2018年4月11日 09:17 in 题解 with tags HDU 欧拉函数 , 83 阅读
转载请注明出处:http://danihao123.is-programmer.com/

有个很好康的结论:

\[\gcd(x^a - 1, x^b - 1) = x^{\gcd(a, b)} - 1\]

然后尝试去用常见套路(枚举gcd)化简柿子,得到:

\[\sum_{k = 1}^n (x^k - 1)\sum_{1\leq a,b\leq n} [\gcd(a, b) = k]\]

推到这里了,看到那个\(\sum_{1\leq a,b\leq n} [\gcd(a, b) = k]\)可能很多同学准备直接上莫比乌斯函数了……其实并不需要,其实那个柿子就是:

\[2\sum_{i = 1}^{\lfloor \tfrac{n}{k}\rfloor} \varphi (i) - 1\]

这个意义还是很显然的……更好的一点是这个柿子可以预处理出来,然后整除分块直接搞一波即可。

代码:

#include <cstdio>
typedef long long ll;
const ll ha = 1000000007LL;
const int maxn = 1000005;
const int N = 1000000;
ll phi[maxn], phi_S[maxn];
void sieve() {
  static bool vis[maxn];
  static int prm[maxn]; int cnt = 0;
  phi[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[cnt ++] = i;
      phi[i] = i - 1;
    }
    int v;
    for(int j = 0; j < cnt && (v = i * prm[j]) <= N; j ++) {
      vis[v] = true;
      if(i % prm[j] == 0) {
        phi[v] = (phi[i] * (ll(prm[j]))) % ha;
        break;
      } else {
        phi[v] = (phi[i] * phi[prm[j]]) % ha;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    phi_S[i] = (phi_S[i - 1] + phi[i]) % ha;
  }
  for(int i = 1; i <= N; i ++) {
    phi_S[i] = ((2LL * phi_S[i]) % ha - 1LL + ha) % ha;
  }
}

ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll pre_sum(ll x, ll r) {
  ll p = pow_mod(x, r);
  p = (p - 1LL + ha) % ha;
  p = (p * inv(x - 1LL)) % ha;
  return p;
}
ll seg_sum(ll x, int a, int b) {
  if(x == 1LL) return 0;
  ll len = b - a + 1;
  ll ret = (pre_sum(x, b + 1) - pre_sum(x, a) + ha) % ha;
  ret = (ret - len + ha) % ha;
  return ret;
}
ll calc(ll x, int n) {
  ll ans = 0;
  for(int i = 1; i <= n;) {
    int v = n / i;
    int nx = n / v;
    ll delta = (seg_sum(x, i, nx) * phi_S[v]) % ha;
    ans = (ans + delta) % ha;
    i = nx + 1;
  }
  return ans;
}

int main() {
  sieve();
  int T; scanf("%d", &T);
  while(T --) {
    int x, n; scanf("%d%d", &x, &n);
    printf("%lld\n", calc(x, n));
  }
  return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter