HDU5514 Frogs [容斥(II)]

$F r o g s$

$D e s c r i p t i o n$
$有 m 个石子围成一圈, 有 n 只青蛙跳石子, 都从 0 号石子开始, 每次只能越过 A_{i} 个石子 . 问所有被至少踩过一次的石子的序号之和 .$

$最初想法$

对青蛙 $i$ , 分析其 越过的石子 编号满足的条件,

所以 $i$ 到达的石子编号为 $g c d (M, A_{i})$ 的倍数
证明可以看这里

预处理出每个青蛙的 $B_{i} = g c d (M, A_{i})$ , 排序去重 后进行容斥 , 等差数列求和即可 .

若存在 $B_{i} ∣ B_{j}$ , 则 $B_{j}$ 可以舍去, 不影响答案.
以此作为一个优化.

容斥的 $D F S$ 过程中, 含有参数 $L c m$ , 若 $L c m > M$ , 则直接可以跳出.
以此作为一个剪枝.

从大到小排序, 减少 $D F S$ 的搜索次数,
以此作为一个优化.

已经优化到底了… 上方算法却还是 $T L E$

虽然如此, 也贴一个代码以纪念 .

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define reg register
typedef long long ll;

const int maxn = 1e4 + 5;

int Test_cnt;
int n;
int m;
int len;
int a[maxn];
int b[maxn];
bool Used[maxn];

ll ans;

int gcd(int a, int b){ return !b?a:gcd(b, a%b); }

void dfs(int k, bool opt, int sum){
        if(m/sum-1 <= 0) return ;
        if(k == len+1){
                if(sum == 1) return ;
                ll n = m/sum;
                if(opt & 1) ans += 1ll*n*(n-1)/2 * 1ll*sum;
                else ans -= 1ll*n*(n-1)/2 * 1ll*sum;
                return ;
        }
        dfs(k+1, opt, sum);
        int tmp = sum/gcd(sum, b[k]);
        if(1ll*tmp*b[k] <= 1ll*m) dfs(k+1, opt^1, tmp*b[k]);
}

void work(){
        scanf("%d%d", &n, &m);
        for(reg int i = 1; i <= n; i ++){
                scanf("%d", &a[i]);
                b[i] = gcd(m, a[i]);
        }
        std::sort(b+1, b+n+1);
        len = std::unique(b+1, b+n+1) - b-1;
        int tmp = 0; ans = 0;
        memset(Used, 0, sizeof Used);
        for(reg int i = 1; i <= n; i ++)
                if(b[i] > m/2){
                        ll n = m/b[i];
                        ans += 1ll*n*(n-1)/2 * 1ll*b[i];
                        Used[i] = 1;
                }
        for(reg int i = 1; i <= n; i ++)
                if(!Used[i]) b[++ tmp] = b[i];
        len = tmp;
        std::sort(b+1, b+len+1);
        std::reverse(b+1, b+len+1);
        dfs(1, 0, 1);
        printf("Case #%d: %lld\n", ++ Test_cnt, ans);
}

int main(){
        int t;
        scanf("%d", &t);
        while(t --) work();
        return 0;
}

$正解部分$
到达的石子编号一定为 $M$ 的约数 .

对 $M$ 分解因数, 存到 $F a c t o r []$ 中.
对每个 $g c d (A_{i}, M)$ 的倍数, 若为 $M$ 的因子, 标记 $U s e d [j] = 1$ . (第j个因子), 表示这个石子要被踩 .
从小到大枚举每个因子, 在将此因子计入答案的同时, 将此因子的所有倍数(也为因子)提前标记, 到倍数计算答案时 减去重复.
时间复杂度 $O (N \sqrt{M})$ .

$实现部分$

在输入 $A []$ 时, 要标记其到达的点, 不去暴力标记,
而是枚举每个 $M$ 的约数 $f a c_{j}$ , 若 $f a c_{j} % g c d (M, A_{i}) = = 0$ , 则表示 $f a c_{j}$ 可以到达 , $G o a l [i] = 1$ .
此方法缩小了标记范围.
对每个可能踩到的石子, 即 $M 的约数$ , 记录 $R e p []$ 数组,
踩第 $i$ 个石子的同时, 将其倍数的 $R e p []$ 数组全部加上 $G o a l [i] - R e p [i]$ .

#include<cstdio>
#include<cstring>
#include<algorithm>
#define reg register
typedef long long ll;

const int maxn = 1e5 + 10;

int Test_cnt;
int N;
int M;
int fac_cnt;

int Fac[maxn];
int Goal[maxn];
int Rep[maxn];

ll Ans;

int Gcd(int a, int b){ return !b?a:Gcd(b, a%b); }

void Work(){
        memset(Goal, 0, sizeof Goal);
        memset(Rep, 0, sizeof Rep);
        scanf("%d%d", &N, &M);
        fac_cnt = 0;
        for(reg int d = 1; d*d <= M; d ++){
                if(M % d) continue ;
                Fac[++ fac_cnt] = d;
                if(M/d != d) Fac[++ fac_cnt] = M/d;
        }
        std::sort(Fac+1, Fac+fac_cnt+1);
        for(reg int i = 1; i <= N; i ++){
                int x; scanf("%d", &x);
                x = Gcd(x, M);
                for(reg int j = 1; j <= fac_cnt; j ++) Goal[j] |= Fac[j]%x==0;
        }
        ll Ans = 0;
        for(reg int i = 1; i <= fac_cnt; i ++){ 
                ll n = M / Fac[i]; 
                Ans += n*(n-1)/2*Fac[i] * (Goal[i] - Rep[i]); 
                if(Goal[i] != Rep[i]) 
                        for(reg int j = i+1; j <= fac_cnt; j ++) 
                                if(Fac[j] % Fac[i] == 0) Rep[j] += Goal[i]-Rep[i];
        }
        printf("Case #%d: %lld\n", ++ Test_cnt, Ans);
}

int main(){
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}