# POJ 2195: Going Home (SPFA minimum cost maximum stream)

2023-01-25   ES

## Question:

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;
}
``````

source