hdu1695GCD（欧拉函数+容斥原理）

时间：2022-12-14 05:09:59 作者：哈密综合材料收藏本文下载本文

“哈密”通过精心收集，向本站投稿了8篇hdu1695GCD（欧拉函数+容斥原理），下面就是小编给大家分享的hdu1695GCD（欧拉函数+容斥原理），希望大家喜欢!

目录
第1篇：hdu1695GCD（欧拉函数+容斥原理）第2篇：hdu4135Coprime（欧拉函数+容斥原理）第3篇：hdu 5212（容斥原理）第4篇：容斥原理五年级试题第5篇：容斥原理五年级试题第6篇：HDOJ 4135 Coprime 容斥原理第7篇：ZOJ 3868(容斥原理+快速幂)第8篇：树形图计数之容斥原理练习题

篇1：hdu1695GCD（欧拉函数+容斥原理）

GCDTime Limit:3000MSMemory Limit:32768KB64bit IO Format:%I64d & %I64uSubmit StatusAppoint description:

Description

Given 5 integers: a, b, c, d, k, you‘re to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you‘re only required to output the total number of different number pairs.

Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.

Yoiu can assume that a = c = 1 in all test cases.

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than 3,000 cases.

Each case contains five integers: a, b, c, d, k, 0< a<= b<= 100,000, 0< c<= d<= 100,000, 0<= k<= 100,000, as described above.

Output

For each test case, print the number of choices. Use the format in the example.

Sample Input

21 3 1 5 11 11014 1 14409 9

Sample Output

Case 1: 9Case 2: 736427

Hint

For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).

题目大意：求1到b内x，1到d内y，gcd(x,y)= k 的对数，二元组无序，要求不重复

x和y的最大公约数都是k，也就是说x，y都是k的倍数，b /= k , d /= k 得到新的区间，需要找到新区间的中互质的对数，要求不重复，所以使大的数为b，小的数为d ，从1到b遍历-->i，当i小于等于d时，ans加上i的欧拉函数值，当i大于d时，计算1到d中与i互质的个数，累加得到最后的结果，

hdu1695GCD（欧拉函数+容斥原理）

，

为防止超时，要将欧拉函数值提前处理好，还有将一个数的分解也要预处理。

#include#include#include using namespace std ;#define LL __int64#define maxn 110000LL euler[maxn] ;//记录1到i的欧拉函数和LL p[maxn][30] , p_num[maxn] ; //质因子个数void sieve{ LL i , j ; memset(p_num,0,sizeof(p_num)) ; memset(p,0,sizeof(p)) ; memset(euler,0,sizeof(euler)) ; for(i = 1 ; i< maxn ; i++) euler[i] = i ; for(i = 2 ; i< maxn ; i++) { if( euler[i] == i ) {euler[i] = i-1 ;//是=素数p[i][p_num[i]++] = i ;for(j = 2*i ; j< maxn ; j += i){ p[j][ p_num[j]++ ] = i ; euler[j] = euler[j] * (i-1) / i ;} } euler[i] += euler[i-1] ; }}int cop(int n,int m){ int i , j , num , temp , x = 1<

b ? a : b ;}int min(int a,int b){ return a >b ? b : a ;}LL f(int a,int b){ int n = max(a,b) , m = min(a,b) ; LL num = euler[m] ; for(int i = m+1 ; i<= n ; i++) num += cop(m,i) ; return num ;}int main(){ int a , b , c , d , k ; int t , tt ; sieve() ; scanf(“%d”, &t) ; for(tt = 1 ; tt<= t ; tt++) { scanf(“%d %d %d %d %d”, &a, &b, &c, &d, &k) ; if(k == 0 || k >b || k >d) {printf(“Case %d: 0\n”, tt);continue ; } printf(“Case %d: %I64d\n”, tt, f(b/k,d/k) ); } return 0;}

篇2：hdu4135Coprime（欧拉函数+容斥原理）

Co-primeTime Limit:1000MSMemory Limit:32768KB64bit IO Format:%I64d & %I64uSubmit StatusAppoint description:

Description

Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.

Two integers are said to be co-prime or relatively prime if they have no common positive divisors other than 1 or, equivalently, if their greatest common divisor is 1. The number 1 is relatively prime to every integer.

Input

The first line on input contains T (0< T<= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1<= A<= B<= 1015) and (1<=N<= 109).

Output

For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

Sample Input

21 10 23 15 5

Sample Output

Case #1: 5Case #2: 10

Hint

In the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

题目大意：计算a到b内，与n互质的个数

分别统计1到a-1中，和1到b中与n互质的数，在相减，求1到m中与n互质的数，先求1到m中与n不互质的数的个数，

hdu4135Coprime（欧拉函数+容斥原理）

，

求出n分解后的质数个数，用二进制数表示第i个质数的选和不选，得到m内包含的个数，当选了奇数个质数是，统计的结果累加，为偶数个时，减去。

#include#include#include using namespace std ;#define LL __int64int prim[1000000] , vis[1000000] , cnt ;void sieve(){ memset(vis,0,sizeof(vis)) ; cnt = 0 ; LL i , j ; for(i = 2 ; i<= 1000000 ; i++) { if( !vis[i] ) { prim[cnt++] = i ; for(j = i*i ; j< 1000000 ; j += i) vis[j] = 1 ; } }}LL p[1000] , p_num ;LL f(LL n,LL m){ LL k = n , temp , ans = 0 ; int i , j , num ; for(i = 0 , p_num = 0 ; i< cnt ; i++) { if( k % prim[i] == 0 ) {p[p_num++] = prim[i] ; } while( k % prim[i] == 0 ) {k /= prim[i] ; } if(k == 1)break ; } if( k >1 ) p[p_num++] = k ; for(i = 1 ; i< (1<

篇3：hdu 5212（容斥原理）

Code

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 77 Accepted Submission(s): 27

Problem Description WLD likes playing with codes.One day he is writing a function.Howerver,his computer breaks down because the function is too powerful.He is very sad.Can you help him?

The function:

int calc

{

int res=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

{

res+=gcd(a[i],a[j])*(gcd(a[i],a[j])-1);

res%=10007;

}

return res;

}

Input There are Multiple Cases.(At MOST10)

For each case:

The first line contains an integerN(1≤N≤10000).

The next line containsNintegersa1,a2,...,aN(1≤ai≤10000).

Output For each case:

Print an integer,denoting what the function returns.

Sample Input

51 3 4 2 4

Sample Output

64Hintgcd(x,y) means the greatest common divisor of x and y.

Source BestCoder Round #39 ($)

Recommend hujie | We have carefully selected several similar problems for you: 5213 5209 5208 5205 5204

给你一个a数组，让你计算那段代码的结果，用容斥原理就ok，莫比乌斯反演也行，不过不会莫比乌斯反演（也是容斥原理）orz，

hdu 5212（容斥原理）

，

。。改天学习下。

代码如下：

#include#include#include#include#include#includeusing namespace std;typedef long long ll;const int maxn = 1e4 + 10;const ll mod = 10007;#define rep(i,a,b) for(int i=(a);i<(b);i++)#define pb push_backint cnt[maxn],a[maxn];ll d[maxn];int main{ int n; while(~scanf(“%d”,&n)) {int Mgcd = 1;for(int i = 0; i < n; i++) { int x; scanf(“%d”,&x); Mgcd = max(Mgcd,x); a[i] = x;}memset(cnt,0,sizeof(cnt[0])*Mgcd+20);for(int i = 0; i < n; i++)cnt[a[i]]++;ll ans = 0,res = 0;/*d[i]表示任取两数gcd为i的方案数*/for(ll i = Mgcd; i >0; i--) { ll tot = 0; for(ll j = i; j <= Mgcd; j+= i) { tot += cnt[j]; d[i] = (d[i]-d[j])%mod;/*减去gcd为i的倍数的方案数(容斥原理)*/ } /*gcd为i的方法数等于任选两个数(可重)是i的倍数的方案除去gcd为i的倍数的情况(前面已经减掉了)*/ d[i] = (d[i] + tot*tot)%mod; ans = (d[i]*i*i)%mod; res = (res+i*d[i])%mod;}cout<<((ans-res)%mod+mod)%mod<

篇4：容斥原理五年级试题

1、在1到500的全部自然数中，不是7的倍数，也不是9的倍数的数共有多少个?

2、六年级一班有45名同学，每人都参加暑假体育培训班，其中足球班报25人，篮球班报20人，游泳班报30人，足球、篮球都报者有10人，足球、篮球都报者有12人。问三项都报的有多少人?

3、某校六年级二班有49人参加了数学、英语、语文学习小组，其中数学有30人参加，英语有20人参加，语文小组有10人参加，老师告诉同学既参加数学又参加语文小组的有3人，既参加数学又参加英语和既参加英语又参加语文的人数均为质数，而三种全参加的只有1人，求既参加英语又参加数学小组的人数。

4、某班同学参加升学考试，得满分的人数如下：数学20人，语文20人，英语20人，数学、英语两科满分者8人，数学、语文两科满分者7人，语文、英语两科满分者9人，三科都没有得满分者3人。问这个班最多多少人?最少多少人?

5、向50名同学调查春游去颐和园还是去动物园的态度，赞成去颐和园的人数是全体的35，其余不赞成;赞成去动物园的比赞成去颐和园的学生多3人，其余不赞成，另外对去两处都不赞成的学生数比对去两处都赞成的学生数的13多1人，同时去颐和园和去动物园都赞成和都不赞成的学生各有多少人?

6、分母是1001的最简真分数共有多少人?

7、李老师出了两道数学题，全班40人中，第一有30人做对，第二题有12人未做对，两题都做对的有20人。

(1)第2题对第1题不对有几个人?

(2)两题都不对的有几人?

8、每边长为10厘米的正方形纸片，正中间挖一个正方形的洞，成为宽1厘米的方框，把五个这样的方框放在桌面上，成为如的图案。问桌面上放这些方框盖住部分的面积是多少平方厘米?

9、一次数学竞赛都是填空题，小明答错的恰是题目总数的14，小亮答错5题，两人都答错的题目的总数的16，已知小明，小亮都答对题目超过了试题总数的一半，则他们都答对了多少道题?

10、在1到1998的自然数中，能被2整除，但不能被3或7整除的数有多少个?

篇5：容斥原理五年级试题

1、全班有46名同学,仅会打乒乓球的有18人,会打乒乓球以及会打羽毛球的有7人,不会打乒乓球又不会打羽毛球的.有6人,问,仅会打羽毛球的有多少人?

2、电视台向100人调查昨天收看电视情况，有62人看过2频道，34人看过8频道，11人两个频道都看过。问：两个频道都没有看过的有多少人?

3、一次数学小测验只有两道题，结果全班有10人全对，第一题有25人做对，第二题有18人做错，那么两题都做错的有多少人?

4、在小于100的自然数中既不能被3整除，又不能被2整除的数有多少个?

5、某班45名同学参加了体育测试，其中百米得优者20人，跳远得优者18人，又知百米、跳远均得优者7人，跳高、百米均得优者6人，跳高、跳远均得优者8人，跳高得优者22人，全班只有1名同学各项都没有达到优，求三项都是优的人数。

6、某班四年级时，五年级时和六年级时分别评出10名三好学生，又知四、五年级连续三好生4人，五、六年级连续三好生3人，四年级六年级两年评上三好生的有5人，四、五、六三年没有评过三好生的有20人，问这个班最多有多少名同学?最少有多少名同学?

7、六一儿童节那天，全班45人到颐和园去玩，有33人划了船，20人爬了山。5名同学因身体不好，他们既没有划船也没有爬山，他们游览了长廊。问：既划了船也爬了山的同学有多少人?

8、六(3)班有32人参加数学竞赛，27人参加英语竞赛，22人参加语文竞赛，其中参加英语、数学两科的有12人，参加英语和语文两科的有14人，参加数学和语文两科的有10人，这个班至少有多少人?

9、分母是273的最剪真分数共有多少个?

10、博文学校参加数学竞赛有120名男生，80名女生，参加语文竞赛的有120名女生，80名男生，已知该校总共有260名学生参加竞赛，其中75名男生两科竞赛都参加了，那么只参加数学竞赛而没有参加语文竞赛的女生有多少人?

篇6：HDOJ 4135 Coprime 容斥原理

求得n的因数后,简单容斥

Co-prime

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1798 Accepted Submission(s): 685

Problem Description Given a number N, you are asked to count the number of integers between A and B inclusive which are relatively prime to N.

Input The first line on input contains T (0 < T <= 100) the number of test cases, each of the next T lines contains three integers A, B, N where (1 <= A <= B <= 1015) and (1 <=N <= 109).

Output For each test case, print the number of integers between A and B inclusive which are relatively prime to N. Follow the output format below.

Sample Input

21 10 23 15 5

Sample Output

Case #1: 5Case #2: 10HintIn the first test case, the five integers in range [1,10] which are relatively prime to 2 are {1,3,5,7,9}.

/* ***********************************************Author :CKbossCreated Time :03月27日星期五 17时52分24秒File Name :HDOJ4135.cpp************************************************ */#include#include#include#include #include#include#include#include#include#include#includeusing namespace std;typedef long long int LL;LL A,B,N;vectorpr;void getPr{ LL TN=N,now=2; pr.clear(); while(TN!=1) { if(TN%now==0) { pr.push_back(now); while(TN%now==0) TN/=now; } now++; if(now*now>TN) break; } if(TN!=1) pr.push_back(TN);}LL RET,RET1,RET2;void dfs(int x,LL n,int mark){ for(int i=x,sz=pr.size();i>T_T; while(T_T--) { cin>>A>>B>>N; getPr(); A--; RET=A; dfs(0,A,-1); RET1=RET; RET=B; dfs(0,B,-1); RET2=RET; cout<<“Case #”<

篇7：ZOJ 3868(容斥原理+快速幂)

GCD Expectation

Time Limit: 4 Seconds Memory Limit: 262144 KB

Edward has a set ofnintegers {a1,a2,...,an}. He randomly picks a nonempty subset {x1,x2,…,xm} (each nonempty subset has equal probability to be picked), and would like to know the expectation of [gcd(x1,x2,…,xm)]k.

Note thatgcd(x1,x2,…,xm) is the greatest common divisor of {x1,x2,…,xm}.

Input

There are multiple test cases. The first line of input contains an integerTindicating the number of test cases. For each test case:

The first line contains two integersn,k(1 ≤n,k≤ 106). The second line containsnintegersa1,a2,…,an(1 ≤ai≤ 106).

The sum of values max{ai} for all the test cases does not exceed 2000000.

Output

For each case, if the expectation isE, output a single integer denotesE· (2n- 1) modulo 998244353.

Sample Input

15 11 2 3 4 5

Sample Output

42Author: LIN, Xi

Source: The 15th Zhejiang University Programming Contest

Submit Status 题意：给出一个序列，求这个序列子集gcd的k次方和的期望

容斥原理，

ZOJ 3868(容斥原理+快速幂)

，

。。

#include#include#include#include#include#includeusing namespace std;typedef long long ll;const int maxn = 1e6 + 10;const ll mod = 998244353;#define rep(i,a,b) for(int i=(a);i<(b);i++)#define pb push_backint cnt[maxn],a[maxn];ll d[maxn];ll quick_exp(ll a,int n){ ll res = 1; while(n) { if(n&1)res = res*a % mod; a = a*a % mod; n >>= 1; } return res;}int main(){ int T; scanf(“%d”,&T); while(T--) {int n,k;scanf(“%d%d”,&n,&k);int Mgcd = 1;for(int i = 0; i < n; i++) { int x; scanf(“%d”,&x); Mgcd = max(Mgcd,x); a[i] = x;}memset(cnt,0,sizeof(cnt[0])*Mgcd+20);for(int i = 0; i < n; i++)cnt[a[i]]++;ll ans = 0;/*d[i] 表示子集的gcd为i的方案数*/for(int i = Mgcd; i >0; i--) { int tot = 0; for(int j = i; j <= Mgcd; j+= i) { tot += cnt[j]; d[i] = (d[i]-d[j])%mod;/*容斥*/ } /*任选一个i的倍数的非空子集有2^tot-1种可能*/ d[i] = (d[i]+quick_exp(2,tot)-1)%mod; d[i] = (d[i]+mod)%mod; ans += d[i]*quick_exp(i,k); ans %= mod;}cout<