牛客 Diff-prime Pairs

题意:给定 N ( 1 ≤ N ≤ 1 0 7 ) N(1\le N \le 10^7) N(1≤N≤107)，求有多少对数 ( i , j ) (i,j) (i,j)满足 i g c d ( i , j ) \frac{i}{gcd(i,j)} gcd(i,j)i​和 j g c d ( i , j ) \frac{j}{gcd(i,j)} gcd(i,j)j​均为素数， ( i 1 , j 1 ) , ( i 2 , j 2 ) (i_1,j_1),(i_2,j_2) (i1​,j1​),(i2​,j2​)不同当且 i 1 ! = i 2   o r   j 1 ! = j 2 i_1!=i_2\ or\ j_1!=j_2 i1​!=i2​ or j1​!=j2​

Sol:

i g = p r i m e \frac{i}{g}=prime gi​=prime j g = p r i m e \frac{j}{g}=prime gj​=prime

i = p r i m e ∗ g i=prime*g i=prime∗g j = p r i m e ∗ g j=prime*g j=prime∗g

i ∈ [ 1 , n ] i\in [1,n] i∈[1,n] j ∈ [ 1 , n ] j\in [1,n] j∈[1,n]

这样的 i , j i,j i,j要么是素数对，要么是素数对的倍数

枚举 g g g，则 n g \frac{n}{g} gn​表示 p r i m e prime prime的范围，如果在 n g \frac{n}{g} gn​范围内有 k k k个素数

则说明有 ∣ ( g p 1 , g p 2 , . . . , g p k ) × ( g p 1 , g p 2 , . . . , g p k ) ∣ − k |(gp_1,gp_2,...,gp_k)\times (gp_1,gp_2,...,gp_k)|-k ∣(gp1​,gp2​,...,gpk​)×(gp1​,gp2​,...,gpk​)∣−k对组合是符合要求的

且 i , j ∈ g p 1 , g p 2 , . . . , g p k i,j\in {gp_1,gp_2,...,gp_k} i,j∈gp1​,gp2​,...,gpk​

所以枚举 g g g可以表示出所有素数对和他们的倍数

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int prime[N],st[N],sum[N];
int cnt;
void get_primes(int n)
{
     for(int i=2;i<=n;i++)
     {
     	if(!st[i]) prime[++cnt]=i,sum[i]=1;

            for(int j=1;i*prime[j]<=n;j++)
            {
                st[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        
     }
}
int main()
{     
	 ios::sync_with_stdio(0);
	 cin.tie(0);
	 int n;
	 cin>>n;
	 get_primes(n);
  
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+sum[i];
	 long long ans=0;
     ans=1LL*(cnt-1)*cnt;
	 cout<<ans<<endl;
	 return 0;
}