题目背景

由于本人于26.7.29日犯下弥天大罪，时间紧迫，本题仅一个测试点，且测且珍惜（理解题意为上）

题目描述

一个质数是一个只有两个因数：$1$ 和它自身的正整数。开头几个质数是 $2,3,5,7,11\cdots$。

一个正整数的质因数分解是把它表示为若干质数的积。例如：

• $111$ 的质因数分解是 $3\times 37$；
• $43$ 的质因数分解是 $43$；
• $12$ 的质因数分解是 $2\times 2\times 3$。

对于每个正整数，其质因数分解是唯一的（不考虑乘法中质数的顺序）。

当一个正整数的质因数分解中所有质因数都有至少两位，我们称它是好的。例如：

• $343=7\times 7\times 7$ 不是好的；
• $111=3\times 37$ 不是好的；
• $1111=11\times 101$ 是好的；
• $43=43$ 是好的。

你需要计算 $l$ 和 $r$ 之间好的整数的数量（包括 $l$ 和 $r$）。

输入格式

多组数据。第一行一个整数 $t(1\le t\le 1000)$，表示数据组数。

对于每组数据，一行两个整数 $l,r(2\le l\le r\le 10^{18})$。

输出格式

对于每组数据，一行一个整数，表示 $l$ 到 $r$ 之间好的数字的个数。

输入输出样例 #1

输入 #1

4
2 100
2 1000
13 37
2 1000000000000000000

输出 #1

21
227
7
228571428571428570

神犇代码

作为拓展阅读帮助你理解（不是原题，不要想照抄！）

//题干：求区间[a,b]内能被6整除但不能被f[]中任何一个数整除的整数的个数 
#include<bits/stdc++.h>
using namespace std;
//PS:根据容斥原理，+能被6整除的数，-能被6和f[i]整除的数，+能被6,f[i],f[j]整除的数
//SO,奇数+，偶数-，选货不选用DFS 
int n,f[15],a,b,i;
int ans;
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
void dfs(int x,int sum,int tot){
	if(x>n){
		ans+=(b/sum-(a-1)/sum)*(tot&1?1:-1);
		return;
	}
	dfs(x+1,sum,tot);
	sum/=gcd(sum,f[x]);
	if(sum<=b/f[x])dfs(x+1,sum*f[x],tot+1);
}
int main(){
	cin>>n; 
	for(int i=1;i<=n;i++)cin>>f[i];
	cin>>a>>b;
	dfs(1,6,1);
	cout<<ans;
	return 0;
}