题目链接：

贴一张图吧：

题目意思就是给出四个数字，a，b，c，d，分别代表两个区间[a，b]，[c，d]，从这两个区间里面分别拿一个数字组成（x，y），问x和y互质的组合有多少种。

这道题目好像要用莫比乌斯反演，但是目前没有了解过这个知识点，后续会补上，我用的是打表+容斥定理做的，相比于上一种方法，耗费的时间可能会多很多。我亲测是600到800ms，所以还是很有必要学莫比乌斯反演的。

接下来讲我的思路：两个区间里面所有的组合数是（b-a+1）*（d-c+1）种，我可以先算出不互质的组合的个数，再用总数减去它得到互质的组合数。

首先，假设我要算所有gcd（x，y）=2的组合数，那么在区间[a，b]里面，素因子含有2的数字个数是b/2-（a-1）/2这么多个，在区间[c，d]里面含有2这个素因子的数字的个数是d/2-（c-1）/2这么多。这两个数字相乘就是两个区间中gcd（x，y）=2的组合数字。

假如我们遍历计算1到10000000里面所有的素数（大概660000多一点），那么就会出现重复计算的情况，假如我gcd（x，y）=2和gcd（x，y）=3的情况都计算了一边，那么gcd（x，y）=6的情况就计算了两遍，那么我们就要再减去gcd（x，y）=6的情况的组合数。

这就要用到容斥定理（奇加偶减），假如一个数字n，它不同的素因子有奇数个，那么就加，如果是偶数个就减，并且它某一个素因子个数不能大于1个（6=2*3，它的素因子有2和3，素因子2有且只有一个，素因子3有且只有一个，那么这个数字我们是要计算的，另一个数字12=2*2*3，它的素因子2有2个，那么我们就不用计算它，因为它已经包含在（gcd（x，y）=2）的数量+（gcd（x，y）=3）的数量-（gcd（x，y）=6）里面了）。

那么我们现在就要先打表把所有类似于6（2*3），10（2*5），30（2*3*5），这种相同素因子只有一个的数筛出来（大概6000000个，所以花费时间有点多），然后遍历计算就可以了。

这个打表的过程可以在我们线性筛素数的过程中做到，所以这个打表是线性的。

这里面num[i]代表数字i有多少个不同的素数，例如num[30]=3，（30=2*3*5）。

flag[i]表示数字i是不是所有素数有且只有一个，如果flag[i]=true，那么这个i就是我们要找的数字。数组ok就是把这些数字存起来，等下遍历数组ok就可以了。

打表代码：

void init(){    memset(vis,0,sizeof(vis));    memset(flag,false,sizeof(flag));    cnt=0;//记录素数个数     cc=0;//计录我们要找的数组个数     for(int i=2;i

 

完整代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
        
       
      
     

待补充。。。。。。

来补充了，额，请看下面大佬介绍莫比乌斯反演，完......

补充：