⑨的完美冻青蛙(frog)

⑨的完美冻青蛙(frog)

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

题目描述

输入

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

 

接下来有n行,每一行两个正整数pi 和ei 。

输出

样例输入

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<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
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<b.p;
}
void make()
{
    int i,j;
    int to=sqrt(1000001);
    for(i=2; i<=to; i++)
        for(j=i*i; j<=1000000; j+=i)
            f[j]=1;
    return;
}
void find(int x)
{
    int i;
    int to=sqrt(x);
    for(i=2; i<=to; i++)
    {
        if(!f[i])
        {
            int cnt=0;
            while(x%i==0)
            {
                x=x/i;
                cnt++;
            }
            if(i==2)cout<<cnt<<endl;
            ans[i]+=cnt;
            if(x==1)return;
        }
    }
}
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d%d",&a[i].p,&a[i].e);
    }
    sort(a+1,a+n+1,cmp);
    for(i=2; i<=n; i++)
    {
        if(a[i].p==a[i-1].p)
        {
            a[i].e+=a[i-1].e;
            a[i-1].e=0;
        }
    }
    make();
    for(i=1; i<=n; i++)
    {
        if(a[i].e)
        {
            if(a[i].p==3)
            {
                ans[a[i].p]=a[i].e-1;
                ans[a[i].p-1]+=1;
            }
            else
            {
                ans[a[i].p]=a[i].e-1;
                find(a[i].p-1);
            }
        }
    }
    for(i=2; i<=1000000; i++)
    {
        if(!f[i]&&ans[i])
        {
            printf("%d %d
",i,ans[i]);
        }
    }
    return 0;
}