#1298 : 数论五·欧拉函数

时间限制:

10000ms

单点时限:

1000ms

内存限制:

256MB

描述

小Hi和小Ho有时候会用密码写信来互相联系，他们用了一个很大的数当做密钥。小Hi和小Ho约定了一个区间[L,R]，每次小Hi和小Ho会选择其中的一个数作为密钥。

小Hi：小Ho，这次我们选[L,R]中的一个数K。

小Ho：恩，小Hi，这个K是多少啊？

 

小Hi：这个K嘛，不如这一次小Ho你自己想办法算一算怎么样？我这次选择的K满足这样一个条件：

假设φ(n)表示1..n-1中与n互质的数的个数。对于[L,R]中的任意一个除K以外的整数y，满足φ(K)≤φ(y)且φ(K)=φ(y)时，K

也即是K是[L,R]中φ(n)最小并且值也最小的数。

小Ho：噫，要我自己算么？

小Hi：没错！

小Ho：好吧，让我想一想啊。

<几分钟之后...>

小Ho：啊，不行了。。感觉好难算啊。

小Hi：没有那么难吧，小Ho你是怎么算的？

小Ho：我从枚举每一个L,R的数i，然后利用辗转相除法去计算[1,i]中和i互质的数的个数。但每计算一个数都要花好长的时间。

小Hi：你这样做的话，时间复杂度就很高了。不妨告诉你一个巧妙的算法吧：

输入

第1行：2个正整数, L,R，2≤L≤R≤5,000,000。

输出

 

第1行：1个整数，表示满足要求的数字K

样例输入     4 6 样例输出     4   利用欧拉函数的性质，可以在O(N)的时间内求出每个数的函数值。   欧拉函数定义:　　小于n的正整数中与n互质的数的个数。   对于欧拉函数，有一下三个性质：1

若n为素数，则φ(n) = n - 1.

　　　　　　　　　　　　　　  2 若n = p^k，p为素数（即n为单个素数的整数幂），则φ(n) = (p-1)*p^(k-1).

　　　　　　　　　　　　　　  3 若p和q互质，则φ(p*q) = φ(p) * φ(q).

  有了这三个性质，我们便能推出两个定理：　　若p为质数，n为任意整数：

(1) 若p为n的约数，则φ(n*p) = φ(n) * p；

(2) 若p为不为n的约数，则φ(n*p) = φ(n) * (p-1);

于是，据这两条定理，当我们得到一个n时，可以枚举质数p来递推的求解φ(n*p)，这就和欧拉筛是一样的了。

1 #define ll long long 2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #include
             
               7 #include
              
                8 #include
               
                 9 #include
                
                 10 #include
                 
                  11 #include
                  
                   12 #include