本文共 895 字，大约阅读时间需要 2 分钟。

题目地址：

题意：求1~n!中与m!互质的数的个数，且m<=n(1 < = n , m < = 10000000) 思路：因为m<=n，所以m！能被n！整除，那么我们很容易推出下面结论： 对于两个正整数n和m，，如果n是m的倍数，那么1~n中与m互质的数的个数为n/m*Eular(m)。 因为欧拉函数的通式为：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)。所以对于本题目来说，答案如下： 其中pi为<=m的所有素数，因为对于1-1/pi=(pi-1)/pi=(pi-1)*inv(pi)，所以这里要用到逆元，对于1~p中模p的逆元，如果p很大，那么有一个递推式可以求逆元：inv[i]=(m-m/i)*inv[m%i]%m,初始化inv[1]=1。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include