关键词：
题意：有n只青蛙，每只青蛙的弹跳能力为ai，他们都从0出发，绕着m个石头围成的圈子跳跃，石头编号为0~m-1，问能被跳到的石头编号之和。
分析：
1、弹跳能力为ai的青蛙，可以跳到的石头编号是gcd(ai, m)的倍数。
2、枚举m的因子，若某个青蛙可以弹跳的石头编号中有该因子，那证明编号为这个因子的石头一定会被跳到，vis[i] = 1。
3、num[i]记录编号为i的石头被跳了几次，如果被跳的次数不等于应跳的次数，则减去多余的影响。---容斥原理
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define lowbit(x) (x & (-x))
const double eps = 1e-8;
inline int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a > b ? 1 : -1;
}
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 10000 + 10;
const int MAXT = 10000 + 10;
using namespace std;
int gcd(int a, int b){
return !b ? a : gcd(b, a % b);
}
int a[110];
int vis[MAXN];
int num[MAXN];
int main(){
int T;
scanf("%d", &T);
int kase = 0;
while(T--){
memset(a, 0, sizeof a);
memset(vis, 0, sizeof vis);
memset(num, 0, sizeof num);
int n, m;
scanf("%d%d", &n, &m);
int tmp = (int)sqrt(double(m));
int cnt = 0;
for(int i = 1; i <= tmp; ++i){
if(m % i == 0){
a[cnt++] = i;
if(i * i != m){
a[cnt++] = m / i;
}
}
}
sort(a, a + cnt);
int x;
for(int i = 1; i <= n; ++i){
scanf("%d", &x);
int t = gcd(x, m);
for(int j = 0; j < cnt; ++j){
if(a[j] % t == 0) vis[j] = 1;
}
}
LL ans = 0;
for(int i = 0; i < cnt - 1; ++i){
if(vis[i] != num[i]){
int t = (m - 1) / a[i];
ans += (LL)t * (t + 1) / 2 * a[i] * (vis[i] - num[i]);
t = vis[i] - num[i];
for(int j = i; j < cnt - 1; ++j){
if(a[j] % a[i] == 0){
num[j] += t;
}
}
}
}
printf("Case #%d: %lld
", ++kase, ans);
}
return 0;
}
hdu-5514frogs（容斥原理）
题意：有n只青蛙，每只青蛙的弹跳能力为ai，他们都从0出发，绕着m个石头围成的圈子跳跃，石头编号为0~m-1，问能被跳到的石头编号之和。分析：1、弹跳能力为ai的青蛙，可以跳到的石头编号是gcd(ai,m)的倍数。2、枚举m的因子，... 查看详情
hdu5514frogs(容斥)
FrogsTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):1315 AcceptedSubmission(s):443ProblemDescriptionThereare&n 查看详情
hdu5514frogs容斥思想+gcd银牌题
FrogsTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):1509 AcceptedSubmission(s):498ProblemDescriptionThereare&n 查看详情
hdu-5514frogs(容斥)(代码片段)
...gcd(a[i],M)的倍数。所以把每只青蛙的gcd求出来后就是一个容斥了，容斥主要看代码领悟。如果出现了一个x=gcd 查看详情
做题hdu5514frogs——另类容斥
...一个约数整除的整数和。（n<=10000,m<=1000000000）直接容斥的话，是2^n再拖个log的复杂度，加上当前的数大于m时直接跳出了剪枝，或许会小一点。但是有一个很重要的性质：我们容斥中所有计算过贡献的数，都是m的因数。换言... 查看详情
hdu5514frogs(代码片段)
gcd+容斥1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintmaxn=1e4+10;5lln,m;6intfac[maxn];7intvis[maxn];8intnum[maxn];910intmain()1112intT;13scanf("%d",&T);14for(intii=1 查看详情
hdu5514容斥原理
...。问这些青蛙踩过的石子的编号总和是多少？tags： 容斥经典题。对m分解因子，对每个因子求贡献。#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/S 查看详情
hdu5514容斥原理(代码片段)
FrogsTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):4843 AcceptedSubmission(s):1605ProblemDescriptionThereare& 查看详情
hdu5514frogs(代码片段)
HDU5514Frogs题意：将([0,m))所有符合(a[i]*t~mod~m)的值求和做法：(a[i]*t~mod~m)会在(gcd(a[i],m))的倍数出现，因此问题等价与求：[sum_i=1^m-1[[(a[1],m)|i]or[(a[2],m)|i]or...or[(a[n],m)|i]]i]对于一个i，使得(gcd(i,m)=g)，当存在一个(gc 查看详情
hdoj5514frogs（容斥原理）(代码片段)
...与m的因子个数相关的算法，因子个数<=200做因子之间的容斥，每一个因子a[i]的贡献t=贡献次 查看详情
hdu5514gameofflyingcircus
HDU5515首先这是一道阅读理解题，建议大家一定要好好地读题，不忽略每一个细节。推荐大家读读这个博客题目翻译思路比较简单，考虑fighter与speeder相遇在#2到#3的线段和相遇在#3和#4的线段的两种情况，分别卡列... 查看详情
容斥原理
容斥原理 对容斥原理的描述 容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。 描述 容斥原理可以描述如下： ... 查看详情
容斥原理
容斥原理 对容斥原理的描述 容斥原理是一种重要的组合数学方法，可以让你求解任意大小的集合，或者计算复合事件的概率。 描述 容斥原理可以描述如下： ... 查看详情
容斥原理
容斥原理（Inclusion–exclusionprinciple），是指在计数时，必须注意无一重复，无一遗漏，为了使重叠部分不被重复计算，人们研究出一种新的计数方法。这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有... 查看详情
容斥原理(代码片段)
...集2，并集（∪）满足任意一个事件即可，则取并集3，容斥原理即先容再斥，以集合为例，求集合并。则可以先单独考虑每个集合，然后直接都加起来，这样的话集合间的交集就会被重复计数，所以就有了容斥原理来消除这个... 查看详情
容斥原理
容斥原理用于计算多个集合并集的大小。[small ext一张用烂的图][small extfromWikipedia]先将所有单个集合的大小计算出来，减去所有两个集合相交的部分，加回所有三个集合相交的部分，减去所有四个集合相交的部分，依此类推，一... 查看详情
关于容斥原理
容斥原理大概是这样的,以长方体体积并为例,我们需要用容斥原理容斥出若干个长方体体积的并.首先,我们将每个长方体标号为1~n,那么这些长方体的取舍显然可以表示为一个二进制的数字S.设F[S]表示长方体取舍状态为S时,长... 查看详情
容斥原理
容斥原理用于计算若干集合的交集以及并集的基数。$$left|igcup_{i=1}^n{X_i} ight|=sum_{k=1}^n{left(-1 ight)^{k+1}sum_{1lei_1<cdots<i_klen}^{}{left|X_{i_1}capcdotscapX_{i_k} ight|}}$$ 下面用归纳法进行证明： 查看详情