⑨的完美冻青蛙(frog)

时间限制: 1 Sec  内存限制: 128 MB

题目描述

 

输入

第一行是一个正整数n,表示上式中的p的个数。

 

 

接下来有n行,每一行两个正整数

p

i

 和

e

i

 。

 

输出

 

样例输入

2 2 2 3 2

样例输出

2 2 3 1

提示

 

样例解释

N=2*2*3*3=36

phi(N）=36*(1-1/2)*(1-1/3)=12 12=2*2*3

样例输入二

4

37 1

3 4

37 1

333667 2

样例输出二

2 4

3 8

37 2

167 1 333667 1

题解：

 

付一个效率不是那么高的代码：

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               using namespace std;int n,m;int ans[1000001],f[1000001];struct node{ int p,e;} a[500001];bool cmp(const node a,const node b){ return a.p