BZOJ 2818: GCD

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.一个很显然的转化:
对一个质数p 求<=N/p 的互质对的个数
即求欧拉函数前缀和
但是N <= 10^7
分解每个数的质因数必跪啊、
然后查了一下题解 发现有个叫线性筛法的东西 我居然不知道= =。。<弱爆了T_T>用这个线性筛法 顺便可以求出欧拉函数
欧拉函数是积性函数
如果(a, b)=1
φ(a*b)=φ(a) * φ(b)

线性筛法程序:

1
2
3
4
5
6
7
8
9
for (ll i = 2; i <= n; i++)
  {
    if (!b[i]) p[m++] = i;
    for (ll j = 0; j < m && p[j] * i <= n; j++)
    {
      b[p[j] * i] = 1;
      if (!(i % p[j])) break;
    }
  }

观察筛法程序
发现 对每个非素数k都有一个素数因子p会遍历到它
如果这个k/p是p的倍数 可以证明φ(k)=φ(k/p)*p
否则φ(k)=φ(p)*φ(k/p)

可以求出所有φ再求前缀和再各种啪啪啪即可~
—————-code——————-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
 
const ll maxn = 10000005;
ll n, f[maxn], b[maxn], p[maxn], m;
 
int main()
{
  cin >> n;
  f[1] = 1;
  for (ll i = 2; i <= n; i++)
  {
    if (!b[i])
    {
      p[m++] = i;
      f[i] = i – 1;
    }
    for (ll j = 0; j < m && p[j] * i <= n; j++)
    {
      f[p[j] * i] = f[i] * p[j];
      b[p[j] * i] = 1;
      if (!(i % p[j])) break;
      f[p[j] * i] = (p[j]1) * f[i];
    }
  }
  ll ans = 0;
  for (ll i = 1; i <= n; i++) f[i] += f[i - 1];
  for (ll i = 1; i <= n; i++) f[i] = f[i] * 21;
  for (ll i = 0; i < m; i++) ans += f[n / p[i]];
  cout << ans;
}

BZOJ 2818: GCD》上有2条评论

发表评论