Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Description
If two trees and Sherlock are in one line, Farmer Sherlock can only see the tree nearest to him.
Input
Output
Sample Input
1 1
2 3
Sample Output
5
容斥原理
题意：给n*m的矩阵有点，左下角的点为(1,1)，右上角的点(n,m)，（其实转回来也是没影响的即m*n），一个人站在（0,0）看这些点，在一条直线的视线上，它只能看到最前面的那个点，后面的点将会被档住他看不到，问你，这个人一共能看到多少个点。
这个问题只要画一下图不难发现，如果一个点(x,y)，x和y有非1的公约数z，那么他们其实可以一起缩小为(x/z,y/z)，试着把这两个点和(0,0)连线，发现他们其实是同一条直线，而(x/z,y/z)
在前面，所以其实(x,y)被挡住了看不到的，这启发了我们，如果我们找到了x和y的最大公约数g，那么(x/g,y/g)一定是这条直线上最前面的点，没有其他店能挡住他，他一定能被看到，而他后面的点都看不到，那么(x/g,y/g)满足的性质就是，这两个数字互质
从而得到一个结论，两个数字(x,y)如果两数互质，则可以被看到，如果不互质，则看不到，所以我们就是要找出所有的二元组(x,y)使他们互质
我们可以固定一个数字，用一个数来循环。例如矩阵为n*m，我们固定m，用n来循环，即1与[1,m]里面多少个数互质，2与[1,m]里面多少个数互质，3与[1,m]里面多少个数互质……n与[1,m]里面多少个数互质，把这些结果全部累加起来即可
所以问题的最后变为了，给定一个数字x，怎么找出它和1到y里面有多少个数互质呢？
两个数字互质，其实就是它们没有公共的质因子，反过来两个数字有公共的质因子则一定不互质，那么我们可以求反面，x与1到y里面多少个数字不互质，然后用y减去即可
在这里我们就用到了容斥原理：先找到有多少个数和x有1个公共的质因子，然后加上；再找到有多少个数与x有2个公共的质因子，然后减去；再找到有多少个数有多少个数与x有3个公共的质因子，然后加上……最后得到的个数，就是有多少个数与x不互质
因为容斥原理一个最基本的准则就是——
要计算几个集合并集的大小，我们要先将所有单个集合的大小计算出来，然后减去所有两个集合相交的部分，再加回所有三个集合相交的部分，再减去所有四个集合相交的部分，依此类推，一直计算到所有集合相交的部分。(奇数加，偶数减)
1.dfs搜索遍历
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e3+;
int prime[maxn],cnt=;
bool isprime[maxn];
void get()
{
for(int i=;i<=maxn;i++)
{
if(!isprime[i])
{
prime[cnt++]=i;
for(int j=i+i;j<=maxn;j+=i)
isprime[j]=;
}
}
}
int data[maxn],k=;
void cal(int n)
{
for(int i=;prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==)
{
data[k++]=prime[i];
while(n%prime[i]==)
n/=prime[i];
}
}
if(n!=)
data[k++]=n;
}
int n,m,t;
ll ans;
void dfs(int hav,int cur,int num)
{
if(hav>m||cur==k)
return ;
for(int i=cur;i<k;i++)
{
int tmp=hav*data[i]; //这里注意
if(num&)
ans-=m/tmp;
else
ans+=m/tmp;
dfs(tmp,i+,num+); //是i+1不是cur+1
}
}
int main()
{
get(); //一定不能忘
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
ans=m;
for(int x=;x<=n;x++)
{
memset(data,,sizeof(data));
k=;
cal(x);
ans+=m;
for(int i=;i<k;i++)
{
ans-=m/data[i];
dfs(data[i],i+,);
}
}
printf("%lld\n",ans);
}
}
2.二进制枚举
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn=1e3+;
int prime[maxn],cnt=;
bool isprime[maxn];
void get()
{
for(int i=;i<=maxn;i++)
{
if(!isprime[i])
{
prime[cnt++]=i;
for(int j=i+i;j<=maxn;j+=i)
isprime[j]=;
}
}
}
int data[maxn],k=;
void cal(int n)
{
for(int i=;prime[i]*prime[i]<=n;i++)
{
if(n%prime[i]==)
{
data[k++]=prime[i];
while(n%prime[i]==)
n/=prime[i];
}
}
if(n!=)
data[k++]=n;
}
int n,m,t;
int main()
{
get(); //一定不能忘
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
ll ans=m;
for(int x=;x<=n;x++)
{
memset(data,,sizeof(data));
k=;
cal(x);
for(int i=;i<(<<k);i++)
{
int flag=;
ll tmp=;
for(int j=;j<k;j++)
{
if(i&(<<j))
{
flag++;
tmp*=data[j];
if(tmp>m)
break;
}
}
if(flag&)
ans-=m/tmp;
else
ans+=m/tmp;
}
}
printf("%lld\n",ans);
}
}