hdu6053

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
", kase++, ans);
    }
    return 0;
}