题目描述

对于一个给定的正整数n，研究它和其它数的最大公约数的值，可以得出许多有趣的性质。 其中一个广为人知的性质就是欧拉函数φ(n)，它表示正整数1~n中与n的最大公约数的值是1的数的个数。

当然，正整数n与正整数1~n的最大公约数并不只会是1， 还可以是其它的数。本题中，你的任务就是找出所有可能的最大公约数的值，并统计正整数1~n中与n的最大公约数是这个值的数有多少个。

 

输入

输入包括一行一个正整数n。

 

输出

输出若干行，每行两个正整数m, x，表示正整数1~n中，有x个数和n的最大公约数为m。

对于每行的mi, xi，你需要保证xi>0，且mi按升序顺序输出。

#include 
      
       #define ll long longusing namespace std;ll n;struct node{    ll x;    ll p;    bool operator<(const node&c)const    {        return x>c.x;    }} now;priority_queue
       
        pi;ll phi(ll x){    ll ret=x;    for (ll i=2;i*i<=x;++i)    {        if (x%i==0)        {            ret-=ret/i;            while(x%i==0)                x/=i;        }    }    if(x>1)    {        ret-=ret/x;    }    return ret;} int main(){    scanf("%lld",&n);    for(ll i=1;i*i<=n;++i)    {        if(n%i==0)        {            now.x=n/i;            now.p=phi(i);            pi.push(now);            if(i*i!=n)            {                now.x=i;                now.p=phi(n/i);                pi.push(now);            }        }    }    while(!pi.empty())    {        now=pi.top();        printf("%lld %lld\n",now.x,now.p);        pi.pop();    }    return 0;}