2015 ACM-ICPC 沈阳区域赛 F:Frogs


题目链接:2015 ACM-ICPC 沈阳区域赛 F:Frogs


Description
m个石子围成一圈, 有n只青蛙跳石子, 都从0号石子开始,
每只能越过x_i个石子。问所有被至少踩过一次的石子的序号之和。


Sample Input
2 12
9 10


Sample Output
42


Solution
对于第i只青蛙,我们可以很容易地想到它踩得到的石头的编号肯定满足,k\cdot gcd(x_i,m)\%m
再考虑多只青蛙,我们同样会非常容易地想到利用容斥去求最终答案,如果不是pps点醒了我,我可能花上大半辈子都写不出qwq %%%pps
我们可以先预处理出来m的所有因子,因为只有m的因子的倍数才有可能满足(k\cdot gcd(x_i,m))\%m,对每一个因子都记一个变量num表示这个因子对最后的答案贡献了几次,并记因子为d,cnt=[d\in\{x|x=k\cdot gcd(x_i,m)\%m\}]
然后再从小到大的处理每个因子d,处理完一个后将其他是d的倍数的因子的num减去dnum


Code

#include<map>
#include<set>
#include<list>
#include<queue>
#include<vector>
#include<string>
#include<time.h>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
//#define Judge
//#define Online
#define maxn 10005
#define reg register
#define ll long long
#define mod 1000000007
#define inf 2147483647
#define lowbit(x) ((x)&-(x))
#define abs(x) ((x)<0?-(x):(x))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define isd(c) ('0'<=(c)&&(c)<='9')
#define isa(c) ('a'<=(c)&&(c)<='z')
#define isA(c) ('A'<=(c)&&(c)<='Z')
#define ckmax(a,b) ((a)=max((a),(b)))
#define ckmin(a,b) ((a)=min((a),(b)))
using namespace std;
#ifdef Judge
#define puts io.put
#define getchar io.gc
#define putchar io.wchar
#ifdef Online
FILE*in=stdin;
FILE*out=stdout;
#else
FILE*in=fopen(".in","r+");
FILE*out=fopen(".out","w+");
#endif
struct FastIO{
    #define S 1000000
    int wpos,len,pos;char wbuf[S],buf[S];
    FastIO(){wpos=0,len=0,pos=0;}
    inline char gc(){
        if (pos==len) pos=0,len=fread(buf,1,S,in);
        if (pos==len) return 0; return buf[pos++];
    }
    inline void wchar(int x) {
        if (wpos==S) fwrite(wbuf,1,S,out),wpos=0;
        wbuf[wpos++]=x;
    }
    inline void put(const char*s) {for(; *s; ) wchar(*s++);}
    ~FastIO() {
        if (wpos) fwrite(wbuf,1,wpos,out),wpos=0;
    }
}io;
#endif
template<typename T> inline void read(T&x){T f=1;x=0;char c;
    for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
    for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c=0){char ch[(sizeof(T)+1)<<1];if (x<0) x=-x,putchar('-');
    int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!=0) putchar(c);
}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
int n,m,cnt,pri[maxn],num[maxn],vis[maxn];ll ans;
int main(int argv,char*argc[]){
    int T;read(T);
    for (int cas=1; cas<=T; ++cas){
        read(n),read(m);cnt=ans=0;
        memset(vis,0,sizeof(vis));
        memset(num,0,sizeof(num));
        for (int i=1,g=sqrt(m); i<=g; ++i)
            if (m%i==0) {pri[++cnt]=i;
                if (i*i!=m) pri[++cnt]=m/i;
            }
        sort(pri+1,pri+cnt+1);
        for (int x,k,i=1; i<=n; ++i){
            read(x),k=gcd(x,m);
            for (int j=1; j<=cnt; ++j)
                if (pri[j]%k==0) vis[j]=1;
        }
        vis[cnt]=0;
        for (int i=1; i<=cnt; ++i)
            if (vis[i]!=num[i]){
                int t=(m-1)/pri[i];
                ans+=1ll*t*(t+1)/2*pri[i]*(vis[i]-num[i]);
                t=vis[i]-num[i];
                for (int j=i; j<=cnt; ++j) if (pri[j]%pri[i]==0) num[j]+=t;
            }
        printf("Case #%d: %lld\n",cas,ans);
    }
    return 0;
}


点我回到主页

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s