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;
}