Mophues HDU - 4746 

题意:[1,n] 和 [1,m]中有多少对数的GCD k,k的素因子个数小于等于p

思路:

我们先解决[1,n],[1,m]有多少对数的GCD为k

分析到这一步,复杂度为 q * n, 不能接受,考虑到在连续的k内(n/k) (m/k)是有重复部分的,可以用分块解决

最后质因数个数P的限制,只要在sum(k)多加一维就可以了

最终复杂度为

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
const int MOD=1e9+7;

int cnt[N];

int mu[N], vis[N], prime[N];
int summu[N];
int tot;//用来记录prime的个数
void init(){
    mu[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!vis[i]){
            prime[tot ++] = i;
            mu[i] = -1;
            cnt[i]=1;
        }
        for(int j = 0; j < tot && i * prime[j] < N; j ++){
            vis[i * prime[j]] = 1;
            cnt[i * prime[j] ] =cnt[i]+1;
            if(i % prime[j]) mu[i * prime[j]] = -mu[i];
            else{
                mu[i * prime[j]] = 0;
                break;
            }
        }
    }
}
int sum[N][30];
void init1(){
    for(int i=1;i<N;i++)
        for(int j=i;j<N;j+=i)
            sum[j][cnt[i]]+=mu[j/i];

    for(int i=1;i<N;i++)
        for(int j=1;j<30;j++)
            sum[i][j]+=sum[i][j-1];

    for(int i=1;i<N;i++)
        for(int j=0;j<30;j++)
            sum[i][j]+=sum[i-1][j];

    return ;
}
int main(void){

    init();
    init1();
    int Q;
    scanf("%d",&Q);
    while(Q--){
        int n,m,p;
        scanf("%d%d%d",&n,&m,&p);
        if(p>=20){
            printf("%lld\n",1ll*n*m);
            continue;
        }
        ll ans=0;
        int mn=min(n,m);
        for(int d=1;d<=mn;d++){
            int ed=min(n/(n/d),m/(m/d));
            /// gcd=[d,ed] n/d,m/d is same
            ans+=1ll*(n/d)*(m/d)*(sum[ed][p]-sum[d-1][p]);
            /// sum[i][j] : 质因子个数<=j,到i数为止的Sigma
            d=ed;
        }
        printf("%lld\n",ans);
    }

    return 0;
}