JS's Blog
0%

Hdu 6035 -TrickGCD (容斥加速）

Posted on Edited on In ,

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=6053

题目大意：
给定数组A，AiA_i为BiB_i的最大取值范围，求问有多少种不同的序列B满足任意[l,r][l,r]区间内，gcd值不为1

分析：
gcd值不为1，即所有数都不互质，均拥有某个质因子，但是可以发现直接容斥的复杂度是O(105)∗O(105)=O(1010)O(10^5)*O(10^5)=O(10^{10})，显然复杂度超标，需要优化，经过学长指导，通过对Ai/pA_i/p的结果进行，分组，可以用每次一次O(log2n)O(log_2n)复杂的二分和一次O(log2n)O(log_2n)的快速幂求得一个分组的答案，每个因子均摊大约log2nlog_2n个分组，一共至多n个因子，所以总计复杂度为O(n(log2n)2)O(n(log_2n)^2)

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>


using namespace std;

typedef long long ll;

const int maxn = 2e5+200;
const int mod = 1e9+7;
int n;
ll ans;

bool isprime[maxn];
ll pf[maxn];
int pn[maxn];
ll arr[maxn];


void init()
{
    memset(isprime,true,sizeof(isprime));
    for (int i = 2; i <= maxn ; i ++)
    {
        if (isprime[i])
        {
            for (int j = i ; j <= maxn ; j+= i)
            {
                if(!pf[j]) pf[j] = i;
                else    pf[j] *= i;
                pn[j]++;
                if (j!=i)   isprime[j] = false;
            }
        }
    }


}

ll qp(ll a ,int n)
{
    ll res = 1;
    while (n)
    {
        if (n&1) res= res*a%mod;
        a  = a*a %mod;
        n >>= 1;
    }
    return res;
}


ll solve(int p)
{
    int i = 1;
    ll res = 1;
    while (i<=n)
    {
        int l = i,r = n+1 ,mid;
        int x = arr[i]/p;
        while (1)
        {
            if (l==r-1)
                break;

            mid = (l+r)>>1;
            if (x==arr[mid]/p)
                l = mid;
            else
                r = mid;
        }

        res = res*qp(x,l-i+1)%mod;
        i = l +1;
    }
    return res%mod;
}


int main() {
    int T,t=1;
    init();
    scanf("%d",&T);

    while (T--)
    {
        ans = 0;
        scanf("%d",&n);
        for (int i = 1 ; i <= n ; i ++)
            scanf("%lld",&arr[i]);

        sort(arr+1,arr+n+1);
        int up = arr[1];
        for (int i = 2 ; i <= up ; i ++)
        {
            if (i!=pf[i])   continue;
            ll tmp = solve(i);
            if (pn[i]&1) ans += tmp%mod;
            else    ans -= tmp%mod;
            ans %=mod;
            ans = (ans+mod)%mod;
        }
        printf("Case #%d: %lld\n",t++,ans%mod);
    }

    return 0;
}