Luogu P4844 LJJ爱数数-白红宇

Luogu P4844 LJJ爱数数

阅读量：325 次

发布时间：2019-03-01

本文共 1883 字，大约阅读时间需要 6 分钟。

gcd(A, g - A) = 1，且满足以下不等式：

(g - A) * A ≤ n

A * g ≤ n

(g - A) * g ≤ n

为了求解满足条件的数对 (A, g) 的个数，可以使用包含-排除原理和 Möbius 反演函数。首先，我们需要预处理每个数的约数，并使用邻接表存储，避免使用向量以防止超时。

代码解释

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         using namespace std;template
          
           T read() { T x = 0; int f = 1; char ch = getchar(); while ((ch < '0') || (ch > '9')) { if (ch == '-') { f = -f; } ch = getchar(); } while ((ch >= '0') && (ch <= '9')) { x = x * 10 + ch - '0'; ch = getchar(); } return x * f;}const int maxn = 1414213;const int maxm = 13288457;int p[maxn + 10], prime[maxn + 10], cnt, mu[maxn + 10], pre[maxm + 10], now[maxn + 10], son[maxm + 10], tot;int add(int a, int b) { pre[++tot] = now[a]; now[a] = tot; son[tot] = b; return 0;}int get_prime() { p[1] = mu[1] = 1; for (int i = 2; i <= maxn; ++i) { if (!p[i]) { prime[++cnt] = i; mu[i] = -1; } for (int j = 1; (j <= cnt) && (i * prime[j] <= maxn); ++j) { int x = i * prime[j]; p[x] = 1; if (i % prime[j] == 0) { mu[x] = 0; break; } mu[x] = -mu[i]; } } for (int i = 1; i <= maxn; ++i) { if (!mu[i]) { continue; } for (int j = 1; j <= maxn / i; ++j) { add(i * j, i); } } return 0;}inline long long solve(int x, int l, int r) { long long ans = 0; for (int i = now[x]; i; i = pre[i]) { int k = son[i]; ans += mu[k] * (r / k - l / k); } return ans;}long long n;int main() { get_prime(); n = read
           
            (); long long ans = 0; int mx = sqrt(2 * n) + 1; for (int i = 2; i <= mx; ++i) { int lower = max(1, i - n / i); int upper = min(n / i, i - 1); if (lower > upper) { continue; } ans += solve(i, lower, upper); } printf("%lld\n", ans); return 0;}