Question:

Question link:http://acm.hdu.edu.cn/showproblem.php?pid=6053
Give a sequence A with a length of n, which requires the design of a sequence B with the same length n, and the request is satisfied:
1. 1 <= b[i] <= a[i]
2. For any interval [L, R], you must meet GCD (a [L], a [L+1] … A [R])> = 2
Ask how many possible B groups are there

thinking:

Analysis of the meaning is actually how many schemes are required to make the entire GCD B of the B array is not 1.
There are two ways to use the Mobius background or DP.

Mobius Reverse:

Set F [D] a scheme with a multiple of N numbers of GCDs D, and F [D] is the number of schemes with n numbers GCD == D.
As long as F [D] is required to calculate f [d], the key is the calculation of f [d], and the enumeration GCD == d. If each D calculates the product of all A [i]/d, it is Obviously T. So use a skill here, as long as you know how many of A [i]/d are the same, you can enumerate the multiple of D, and then use the prefix and the quick power.

dp：

Thinking Mobius is similar, and it is also an enumeration GCD. Here you can set DP [i] as a scheme with GCD == I. Use the solution of f (d) to find DP [d], and then use Rong Rong to Rong Rong to Rong Rong. Remove your mind, you can reduce the extra part, pay attention to the counter -order reduction.

code:

Mobius Reverse:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 +7;
const LL INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;

int u[MAXN], prime[MAXN];
bool vis[MAXN];

void Mobius(int x) {
    int cnt = 0;
    memset(vis, false, sizeof(vis));
    u[1] = 1;
    for (int i = 2; i <= x; i++) {
        if (!vis[i]) {
            prime[++cnt] = i;
            u[i] = -1;
        }
        for (int j = 1; j <= cnt && prime[j] * i <= x; j++) {
            vis[prime[j] * i] = true;
            if (i % prime[j]) u[prime[j] * i] = -u[i];
            else {
                u[prime[j] * i] = 0;
                break;
            }
        }
    }
}

LL pow_mod(LL a, LL n) {
    LL res = 1;
    while (n) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int sum[MAXN];

int main() {
    //freopen("in.txt", "r", stdin);
    Mobius(100000);
    int T, cs = 0;
    scanf("%d", &T);
    while (T--) {
        int n, x, Min = INF, Max = 0;
        memset(sum, 0, sizeof(sum));
        scanf("%d", &n);
        LL ss = 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            sum[x]++;
            Min = min(Min, x);
            Max = max(Max, x);
            ss = ss *x % MOD;
        }
        sum[0] = 0;
        for (int i = 1; i <= Max; i++) {
            sum[i] += sum[i - 1];
        }
        LL ans = 0;
        for (int i = 1; i <= Min; i++) {
            LL tmp = 1;
            for (int j = 1; j <= Max / i; j++) {
                int l = j * i, r = min((j + 1) * i - 1, Max);
                int cnt = sum[r] - sum[l - 1];
                tmp = tmp * pow_mod(j, cnt) % MOD;
            }

            ans = ((ans + u[i] * tmp % MOD) % MOD + MOD) % MOD;
        }
        ans = ((ss - ans) % MOD + MOD) % MOD;
        printf("Case #%d: %I64d\n", ++cs, ans);
    }
    return 0;
}

1+dp:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1e9 +7;
const LL INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;

int dp[MAXN];

LL pow_mod(LL a, LL n) {
    LL res = 1;
    while (n) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int sum[MAXN];

int main() {
    //freopen("in.txt", "r", stdin);
    int T, cs = 0;
    scanf("%d", &T);
    while (T--) {
        int n, x, Min = INF, Max = 0;
        memset(sum, 0, sizeof(sum));
        scanf("%d", &n);
        LL ss = 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &x);
            sum[x]++;
            Min = min(Min, x);
            Max = max(Max, x);
            ss = ss *x % MOD;
        }
        sum[0] = 0;
        for (int i = 1; i <= Max; i++) {
            sum[i] += sum[i - 1];
        }
        for (int i = 1; i <= Min; i++) {
            dp[i] = 1;
            for (int j = 1; j <= Max / i; j++) {
                int l = j * i, r = min((j + 1) * i - 1, Max);
                int cnt = sum[r] - sum[l - 1];
                dp[i] = dp[i] * pow_mod(j, cnt) % MOD;
            }
        }
        for (int i = Min; i >= 2; i--) {
            for (int j = i * 2; j <= Min; j += i) {
                dp[i] = ((dp[i]- dp[j]) % MOD + MOD) % MOD;
            }
        }
        LL ans = 0;
        for (int i = 2; i <= Min; i++) {
            ans = (ans + dp[i]) % MOD;
        }
        printf("Case #%d: %I64d\n", ++cs, ans);
    }
    return 0;
}