利用容斥原理求解范围内互素数对数例题

GCD

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

1
2
3

2
1 3 1 5 1
1 11014 1 14409 9

Sample Output

1 2	Case 1: 9 Case 2: 736427

Hint

1	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]范围内和[1,d]范围内最大公约数为k的二元组的对数

题解：

gcd(a,b)=k，我们可以写成gcd(a/k,b/k)=1。因此我们只需求[1,b/k]和[1,d/k]范围内互素数的对数。首先利用欧拉函数很容易求解[1,min(a,b)]范围内互素数的对数，将φ(1~min(a,b))全部加起来，就求出1~min(a,b)所有互素对数，假设d永远＞=b,那么接下来我们只需求[1,b]范围内和[b+1,d]范围内互素的数，此时需用容斥原理。对于[1,b]范围内和x互素的数，最多为b个，而在这b个数中我们只需减去不互素的对数即可。我们需先求出x的所有质因数，然后这些质因数的倍数在[1,b]范围内的个数为b/g，因此只需减去这些对数即可，然而由于会有重复的情况出现，因此需用容斥原理处理一下。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
typedef long long ll;
ll oula[maxn];
int a,b,c,d,k;
struct Number
{
    int cnt;
    int prime[20];
} fac[maxn];
void getLa( int n)
{
    memset(fac,0,sizeof(fac));
    for(int i = 0; i < n; ++i)
        oula[i] = i;
    for(int i = 2; i < n; ++i)
        if( oula[i] == i )
            for(int j = 1; j*i < n; ++j){
                oula[j*i] -= oula[j*i]/i;
                fac[j*i].prime[fac[j*i].cnt++]=i;
            }
}
ll inc(int index,int b,int m)
{
    ll r=0,t;
    for(int i=index; i<fac[m].cnt; ++i)
    {
        t=b/fac[m].prime[i];//b范围内有多少个数和m的因数为prime[i]
        r+=t-inc(i+1,t,m);//减去这些数就是b范围内和m互质的数的个数。
    }
    return r;
}
ll solve()
{
    b/=k;
    d/=k;
    if(b>d)
        swap(b,d);
    ll ans = 0;
    for(int i = 1; i <= b; ++i)
        ans+=oula[i];
    for(int i=b+1; i<=d; ++i)
        ans+=b-inc(0,b,i);
    return ans;
}
int main()
{
    getLa(maxn);
    int t;
    scanf("%d",&t);
    for(int cas = 1; cas<=t; ++cas){
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
        if(k==0){
            printf("Case %d: 0\n",cas);
            continue;
        }
        printf("Case %d: %lld\n",cas,solve());
    }
    return 0;
}

下面那道和上面这道类似，稍微改一下就好。

Visible Trees

There are many trees forming a m * n grid, the grid starts from (1,1). Farmer Sherlock is standing at (0,0) point. He wonders how many trees he can see.
If two trees and Sherlock are in one line, Farmer Sherlock can only see the tree nearest to him.

Input

The first line contains one integer t, represents the number of test cases. Then there are multiple test cases. For each test case there is one line containing two integers m and n(1 ≤ m, n ≤ 100000)

Output

For each test case output one line represents the number of trees Farmer Sherlock can see.

Sample Input

1
2
3

2
1 1
2 3

Sample Output

1
2

1
5

题意

求解[1,b]范围内和[1,d]范围内最大公约数为k的二元组的对数。当然和上面不同之处在于对数左右数不同也认为不同。(2,3)和(3,2)为不同的对数。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
typedef long long ll;
ll oula[maxn];
int m,n;
struct Number
{
    int cnt;
    int prime[20];
} fac[maxn];
void getLa( int n)
{
    memset(fac,0,sizeof(fac));
    for(int i = 0; i < n; ++i)
        oula[i] = i;
    for(int i = 2; i < n; ++i)
        if( oula[i] == i )
            for(int j = 1; j*i < n; ++j){
                oula[j*i] -= oula[j*i]/i;
                fac[j*i].prime[fac[j*i].cnt++]=i;
            }
}
ll inc(int index,int b,int m)
{
    ll r=0,t;
    for(int i=index; i<fac[m].cnt; ++i)
    {
        t=b/fac[m].prime[i];
        r+=t-inc(i+1,t,m);
    }
    return r;
}
ll solve()
{
    if(m>n)
        swap(m,n);
    ll ans = 0;
    for(int i = 1; i <= m; ++i)
        ans+=oula[i];
    ans=ans*2-1;
    for(int i=m+1; i<=n; ++i)
        ans+=m-inc(0,m,i);
    return ans;
}
int main()
{
    getLa(maxn);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&m,&n);
        printf("%lld\n",solve());
    }
    return 0;
}

跳蚤

Z城市居住着很多只跳蚤。在Z城市周六生活频道有一个娱乐节目。一只跳蚤将被请上一个高空钢丝的正中央。钢丝很长，可以看作是无限长。节目主持人会给该跳蚤发一张卡片。卡片上写有N+1个自然数。其中最后一个是M，而前N个数都不超过M，卡片上允许有相同的数字。跳蚤每次可以从卡片上任意选择一个自然数S，然后向左，或向右跳S个单位长度。而他最终的任务是跳到距离他左边一个单位长度的地方，并捡起位于那里的礼物。
比如当N=2，M=18时，持有卡片(10, 15, 18)的跳蚤，就可以完成任务：他可以先向左跳10个单位长度，然后再连向左跳3次，每次15个单位长度，最后再向右连跳3次，每次18个单位长度。而持有卡片(12, 15, 18)的跳蚤，则怎么也不可能跳到距他左边一个单位长度的地方。
当确定N和M后，显然一共有M^N张不同的卡片。现在的问题是，在这所有的卡片中，有多少张可以完成任务。

Input

两个整数N和M(N <= 15 , M <= 100000000)。

Output

可以完成任务的卡片数。

Sample Input

2 4

Sample Output

Hint

这12张卡片分别是：
(1, 1, 4), (1, 2, 4), (1, 3, 4), (1, 4, 4), (2, 1, 4), (2, 3, 4),
(3, 1, 4), (3, 2, 4), (3, 3, 4), (3, 4, 4), (4, 1, 4), (4, 3, 4)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long int
using namespace std;
const int maxn = 1005,maxm = 100005,INF = 1000000000;

LL N,M;
int fac[maxn],faci = 0;

void Sp(){
	LL e = M;
	for (LL i = 2; i * i <= e; i++){
		if (e % i == 0){
			fac[++faci] = i;
			while (e % i == 0) e /= i;
		}
	}
	if (e - 1) fac[++faci] = e;
}

LL qpow(LL a,LL b){
	LL ans = 1;
	for (; b; b >>= 1, a *= a)
		if (b & 1) ans *= a;
	return ans;
}

LL cal(int s){
	LL mult = 1,pos = 1;
	for (int i = 1; s; i++,s >>= 1){
		if (s & 1){
			mult *= fac[i];
			pos *= -1;
		}
	}
	return qpow(M/mult,N) * pos;
}