[HDU 5780]gcd

danihao123 posted @ 2018年4月11日 09:17 in 题解 with tags HDU 欧拉函数 , 586 阅读
转载请注明出处: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;
}
NCERT English Sample 说:
Sep 26, 2022 01:31:26 AM

Teaching Staff of Leading Educational Institutes have prepared these NCERT 10th Class English Sample Papers 2023 all important questions which has been repeatedly asked in previous years old exams. NCERT English Sample Paper Class 10 These NCERT English Question Bank for Reading, Writing, Grammar and Literature questions are prepared from the newly revised syllabus which is listed here.Teaching Staff of Leading Educational Institutes have prepared these NCERT 10th Class English Sample Papers 2023 all important questions which has been repeatedly asked in previous years old exams.


登录 *


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