H、Diff-prime Pairs----简单数论欧拉筛+前缀和+划分思维

主要思想：先把素数筛出来，然后前缀和统计前i个数里有多少素数，然后每次除以最大公约数。
素数对中的素数是不能相同的，其次我们枚举每一个公约数，因为素数对的倍数也是符合题目要求，res += sum[n / g] * (sum[n / g] - 1)

#include
#include
#include
#include
#include
using namespace std;
#define int long long
const int N = 1e7+5;
int primes[N],idx=0;
int st[N];
int cnt[N]={0};
void prime(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])primes[idx++]=i;
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i]=1;
            if(i%primes[j]==0)break;
        }
    }
}
signed main()
{
    int n;
    cin>>n;
    prime(N);
    for(int i=2;i<=n;i++)st[i]^=1;
    for(int i=2;i<=n;i++)st[i]+=st[i-1];
    int res=0;
    for(int i=1;i<=n;i++)res+=st[n/i]*(st[n/i]-1);
    cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5690654.html