HYSBZ 2818 Gcd

Description

給定整數N，求1<=x,y<=N且Gcd(x,y)為素數的

數對(x,y)有多少對.

Input

一個整數N

Output

如題

Sample Input

4

Sample Output

4

Hint

hint

對于樣例(2,2),(2,4),(3,3),(4,2)

1<=N<=10^7

歐拉函數的簡單應用

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 1e7 + 10;
int n, f[N], phi[N], g[N], sz;
LL sum[N];

void init()
{
  sum[0] = sz = 0; sum[1] = phi[1] = 1;
  for (int i = 2; i < N; i++)
  {
    if (!f[i]) { g[sz++] = i; phi[i] = i - 1; }
    for (int j = 0, k; j < sz&&g[j] * i < N; j++)
    {
      f[k = g[j] * i] = 1;
      phi[k] = phi[i] * (g[j] - 1);
      if (i % g[j] == 0) { phi[k] = phi[i] * g[j]; break; }
    }
    sum[i] = sum[i - 1] + 2 * phi[i];
  }
}

int main()
{
  init();
  while (scanf("%d", &n) != EOF)
  {
    LL ans = 0;
    rep(i, 0, sz - 1)
    {
      if (g[i] > n) break;
      ans += sum[n / g[i]];
    }
    printf("%lld\n", ans);
  }
  return 0;
}