hdu 4135 Co-prime(容斥原理)
來源：程序員人生 發布時間：2014-11-07 08:21:30 閱讀次數：2554次
http://acm.hdu.edu.cn/showproblem.php?pid=4135
求連續區間[a,b]內與n互質的數的個數。
由于a,b相當大，斟酌用容斥原理。只需先求出[a,b]內與n不互質的數的個數，等于[1,b]內與n不互質的個數 - [1,a⑴]內與n不互質的個數。問題轉化為求【1，m】內與n不互質的數的個數。
先對n分解質因子，[1,m]內是n的質因子的倍數的那些數肯定與n不互質，但是有許多重復的，需要減去。質因子解法有多種，隊列數組或狀態緊縮。
例如30的質因子是2,3,5，[1,m]內與30互質的數的個數表示為 n/2 + n/3 + n/5 - n/(2*3) - n/(2*5) - n/(3*5) + n/(2*3*5)。發現質因子個數是奇數的做加法，是偶數的做減法。隊列數組解法為摹擬1個隊列，初始將1加入隊列，以后每次取出n的1個質因子順次與隊列中的數相乘后置于隊尾，每次乘⑴決定其前面的正負號。最后隊列里的就是上式所有的份子，然后解之。 狀態緊縮便是將取出的質因子置為1沒取出的置為0，得到1個數res，若res的質因子個數是奇數就加上，是偶數就減，求和就是與m不互素的數的個數，解之。
狀態緊縮
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
//#define LL long long
#define eps 1e⑼
#define PI acos(⑴.0)
using namespace std;
const LL INF = 1<<30;
const int maxn = 100010;
LL a,b,n;
LL ans;
int fac[maxn];
int prime[maxn];
int facCnt;
void getPrime()
{
bool flag[maxn];
memset(flag,false,sizeof(flag));
prime[0] = 0;
for(int i = 2; i < maxn; i++)
{
if(flag[i] == false)
prime[++prime[0]] = i;
for(int j = 1; j <= prime[0]&&i*prime[j]<maxn; j++)
{
flag[i*prime[j]] = true;
if(i % prime[j] == 0)
break;
}
}
}
void getFac()
{
LL tmp = n;
facCnt = 0;
for(int i = 1; i <= prime[0] && prime[i]*prime[i] <= tmp; i++)
{
if(tmp % prime[i] == 0)
{
fac[facCnt++] = prime[i];
while(tmp%prime[i] == 0)
tmp /= prime[i];
}
if(tmp == 1)
break;
}
if(tmp > 1)
fac[facCnt++] = tmp;
}
LL solve(LL m)
{
//位運算
LL anw = 0;
for(int i = 1; i < (1<<facCnt); i++)
{
LL res = 1;
int cnt = 0;
for(int j = 0; j < facCnt; j++)
{
if(i & (1<<j))
{
res *= fac[j];
cnt++;
}
}
if(cnt & 1)
anw += m/res;
else
anw -= m/res;
}
return anw;
}
int main()
{
int test;
scanf("%d",&test);
getPrime();
for(int item = 1; item <= test; item++)
{
scanf("%I64d %I64d %I64d",&a,&b,&n);
getFac();
ans = (b-solve(b)) - (a⑴-solve(a⑴));
printf("Case #%d: %I64d
",item,ans);
}
return 0;
}
隊列數組
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
//#define LL long long
#define eps 1e⑼
#define PI acos(⑴.0)
using namespace std;
const LL INF = 1<<30;
const int maxn = 100010;
LL a,b,n;
LL ans;
int fac[maxn];
int prime[maxn];
int facCnt;
void getPrime()
{
bool flag[maxn];
memset(flag,false,sizeof(flag));
prime[0] = 0;
for(int i = 2; i < maxn; i++)
{
if(flag[i] == false)
prime[++prime[0]] = i;
for(int j = 1; j <= prime[0]&&i*prime[j]<maxn; j++)
{
flag[i*prime[j]] = true;
if(i % prime[j] == 0)
break;
}
}
}
void getFac()
{
LL tmp = n;
facCnt = 0;
for(int i = 1; i <= prime[0] && prime[i]*prime[i] <= tmp; i++)
{
if(tmp % prime[i] == 0)
{
fac[facCnt++] = prime[i];
while(tmp%prime[i] == 0)
tmp /= prime[i];
}
if(tmp == 1)
break;
}
if(tmp > 1)
fac[facCnt++] = tmp;
}
LL solve(LL m)
{
//隊列數組
int que[110];
int l = 0;
que[l++] = 1;
for(int i = 0; i < facCnt; i++)
{
int k = l;
for(int j = 0; j < k; j++)
que[l++] = fac[i]*que[j]*(⑴);
}
LL anw = 0;
for(int i = 0; i < l; i++)
anw += m/que[i];
return anw;
}
int main()
{
int test;
scanf("%d",&test);
getPrime();
for(int item = 1; item <= test; item++)
{
scanf("%I64d %I64d %I64d",&a,&b,&n);
getFac();
ans = solve(b) - solve(a⑴);
printf("Case #%d: %I64d
",item,ans);
}
return 0;
}
dfs
#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL __int64
//#define LL long long
#define eps 1e⑼
#define PI acos(⑴.0)
using namespace std;
const LL INF = 1<<30;
const int maxn = 100010;
LL a,b,n;
LL ans;
LL ans_a,ans_b;
int fac[110];
int facCnt;
void solve(LL num)
{
facCnt = 0;
LL tmp = num;
for(int i = 2; i <= sqrt(tmp+0.5); i++)
{
if(tmp % i == 0)
{
fac[facCnt++] = i;
while(tmp % i == 0)
tmp /= i;
}
}
if(tmp > 1)
fac[facCnt++] = tmp;
}
void dfs(int len, int flag, LL num)
{
if(len == facCnt)
{
if(flag == 0)
{
ans_a += a/num;
ans_b += b/num;
}
else
{
ans_a -= a/num;
ans_b -= b/num;
}
return;
}
dfs(len+1,flag,num);
dfs(len+1,!flag,num*fac[len]);
}
int main()
{
int test;
scanf("%d",&test);
for(int item = 1; item <= test; item++)
{
scanf("%I64d %I64d %I64d",&a,&b,&n);
a -= 1;
ans_a = 0;
ans_b = 0;
solve(n);
dfs(0,0,1LL);
printf("Case #%d: %I64d
",item,ans_b-ans_a );
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
