hdu 6053 TrickGCD(筛法+容斥)

TrickGCD

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2649 Accepted Submission(s): 1007

Problem Description

You are given an array

Input

The first line is an integer T(

Output

For the

Sample Input

4 4 4 4

Sample Output

Case #1: 17

Source

2017 Multi-University Training Contest - Team 2

Recommend

liuyiding | We have carefully selected several similar problems for you: 6066 6065 6064 6063 6062

看范围就知道要去枚举gcd，对于每个gcd，在a[i]这个位置上有gcd/a[i]个数能满足条件构成b[i]，只要把每个位置求出来累乘就好了，但是这个过程还需要优化。

优化可以用素数筛法类似的方式，把gcd/a[i]相同的数都一起处理，这样在用一个快速幂把相同的那些情况数算出来，时间复杂度就是n*logn*logn。

但是答案显然会有重复，赛时就是这个问题不会解决然后gg。

dp[i]表示 gcd=i 时求出的符合情况数，显然它包含了 i 的倍数对应的情况，我们需要把这些数减去，但是倍数的情况显然也有重复，比较复杂。

这个过程我们可以倒过来从上界往下去容斥，这样每次对于num[i]来说，它的倍数的情况都是已经处理好了的，只要依次减去倍数的情况了，其实相当于一个dp的过程。。

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<map>
#include<cmath>
using namespace std;

const long long mod=1e9+7;
int sum[100005],a[100005];
long long dp[100005];

int n,T,k;
long long poww(long long a, long long b)
{
    long long ans=1;
    while(b)
    {
        if (b&1) ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
   return ans;
}
int main()
{
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        memset(sum,0,sizeof(sum));

        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum[a[i]]++;
        }
        for(int i=1;i<=1e5;i++) sum[i]+=sum[i-1];

        for(int i=2;i<=1e5;i++) //  gcd=i
        {
           dp[i]=1;
            for(int j=0;j<=1e5;j+=i)
            {
              if (j+i-1>100000) k=sum[100000]-sum[j-1];
                else if (j==0) k=sum[0+i-1];
                  else k=sum[j+i-1]-sum[j-1]; //k表示a序列中，数字范围在[j，j+i-1]的个数，分段
              int knum=j/i; // 该范围的数字，对于gcd=i的倍数的个数相同

              if (knum==0 && k>0) dp[i]=0; //如果这范围的数字存在，但是，要gcd==i没有数字可选，那么这个gcd无解，不存在可行解
                else dp[i]=(dp[i]*poww(knum,k))%mod;
            }
        }

        for(int i=1e5;i>=2;i--)
            for(int j=i+i;j<=1e5;j+=i)
        {
            dp[i]-=dp[j];
            dp[i]=(dp[i]+mod)%mod;
        }
        long long ans=0;
        for(int i=2;i<=1e5;i++)
                ans=(ans+dp[i])%mod;
        printf("Case #%d: %lld
",cas,ans);
    }
    return 0;
}