6

2015ACM-ICPC亚洲区域赛沈阳站 F：Frogs（容斥）

 4 years ago
source link: https://arminli.com/acm-shenyang-f/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

2015ACM-ICPC亚洲区域赛沈阳站 F：Frogs（容斥）

March 11, 2016

题目链接

题意： m 个石头标记 0~m-1，然后 n 个青蛙开始都在石头 0 上，每个青蛙每次跳 x 块石头，求最后能被青蛙跳上去的石头的值的和。

首先注意到每只青蛙每次跳的石头号为 gcd(x, m)，然后把 m 的所有因子（最多 log2（m）个）拿出来，设 temp 为每个 gcd，将因子中每个 temp 的倍数都标记为 1，然后再用 num 数组代表某个因数被跳跃的次数。

注意一下由于 0~m-1，所以 m 这个数不会被跳上去（其实是 0）。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
long long p[10005];
long long num[10005];//被加了几次
long long vis[10005];
int main(){
    //freopen("a.txt", "r", stdin);
    int t; cin >> t;
    for(int cas = 1; cas <= t; cas++){
        long long ans = 0;
        memset(vis, 0, sizeof(vis));
        memset(num, 0, sizeof(num));
        long long m, n;
        scanf("%lld %lld", &n, &m);
        int cnt = 0;
        //取出m的所有因子
        for(int i = 1; i <= sqrt(m); i++){
            if(m%i == 0){
                p[cnt++] = i;
                if(i*i != m)
                    p[cnt++] = m/i;
            }
        }
        sort(p, p+cnt);
        //对于每个青蛙跳跃的步数分别求出gcd，然后在因子中标记gcd的倍数为1
        for(int i = 0; i < n; i++){
            long long q;
            scanf("%lld", &q);
            int tem = __gcd(q, m);
            for(int j = 0; j < cnt; j++){
                if(p[j]%tem == 0)
                    vis[j] = 1;
            }
        }

        vis[cnt-1] = 0;  //由于0~m-1，所以没有m这个数

        for(int i = 0; i < cnt; i++){
            if(vis[i] != num[i]){
                ans += m*(p[i]+m)/p[i]/2*(vis[i]-num[i]); //若p[i]=2,则求2+4+6+…+m的和
                for(int j = i+1; j < cnt; j++)
                    if(p[j]%p[i] == 0)
                        num[j] += (vis[i]-num[i]);  //更新未计算的num的值
            }
        }
        printf("Case #%d: %lld\n", cas, ans);
    }
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK