hdu6053

题意

给出 \(A\) 数组，问有多少种 \(B\) 数组满足下面条件。

\(1≤ B_i ≤ A_i\)
For each pair \(( l , r ) \ (1≤l≤r≤n) , gcd(b_l,b_{l+1}...b_r) ≥ 2\) 。

分析

首先肯定要去枚举 \(gcd\) ，如果暴力去计算，对于每个 \(gcd\) ，我们都要乘 \(n\) 次，这样显然会超时。考虑一种将区间分块的思想，如果 \(gcd\) 为 \(10\) ，那么区间 \([20, 30)\) 里的数除以 \(10\) 都是 \(2\) ，当 \(gcd\) 越大时，区间越大。我们直接统计下前缀和，可以查询某个区间里包含的数的个数，快速幂计算答案。

最后求得的 \(dp[i]\) 表示 \(gcd=i\) 时，构成的 \(B\) 数组的个数，可以用容斥去处理得到最后的答案。

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

const int N = 1e5 + 5;

const ll MOD = 1e9 + 7;

int kase = 1;

int T;

ll POW(ll x, int n) {

    ll res = 1;

    while(n) {

        if(n & 1) res = res * x % MOD;

        x = x * x % MOD;

        n >>= 1;

    }

    return res;

}

int sum[MAXN];

ll dp[MAXN];

int main() {

    scanf("%d", &T);

    while(T--) {

        memset(sum, 0, sizeof sum);

        memset(dp, 0, sizeof dp);

        int n;

        scanf("%d", &n);

        int mn = N;

        for(int i = 0; i < n; i++) {

            int x;

            scanf("%d", &x);

            mn = min(mn, x);

            sum[x]++;

        }

        for(int i = 1; i <= N; i++) {

            sum[i] += sum[i - 1];

        }

        for(int i = 2; i <= mn; i++) {

            ll c = 0;

            dp[i] = 1;

            for(int j = i; j <= N; j += i) {

                c++;

                int x;

                if(j + i - 1 > N) x = sum[N] - sum[j - 1];

                else x = sum[j + i - 1] - sum[j - 1];

                if(x == 0) continue;

                dp[i] = (dp[i] * POW(c, x)) % MOD;

            }

        }

        for(int i = N; i >= 2; i--) {

            for(int j = 2 * i; j <= N; j += i) {

                dp[i] = (dp[i] - dp[j] + MOD) % MOD;

            }

        }

        ll ans = 0;

        for(int i = 0; i <= N; i++) {

            ans = (ans + dp[i]) % MOD;

        }

        printf("Case #%d: %lld\n", kase++, ans);

    }

    return 0;

}

巴特西

hdu6053

hdu6053

题意

分析

code

最新文章

热门文章