POJ 1365 Prime Land

Input

Output

Sample Input

17 1
5 1 2 1
509 1 59 1
0

Sample Output

2 4
3 2
13 1 11 1 7 1 5 1 3 1 2 1

覺得這題最難的就是理解題意了 應該怪我英語太差了

題意 一個大於1的數可以 表示成p1^e1*p2^e2*p3^e3*p4^e4*p5^e5*...*pn^en的形式 其中p是素數 且p是遞減的 p< 32767

輸入給你這個數的這種表達形式的所有p和e 第奇數個數為pi第偶數個數為ei 每行的所有數據表示一個數 你要求出這個數x然後輸出x-1的這種表達形式；

理解了題意這個題就簡單了 直接暴力可能會超時 所以還是打了個素數表 還要注意pow的前一個參數要乘以1.0 不然會精度丟失

#include
#include
#include
using namespace std;
const int N = 33000;
int x, a, b , m , last , ans[N], vis[N], prime[N];

void initPrime()
{
    int num = 0, m = sqrt (N + 0.5);
    for (int i = 2; i <= m; ++i)
    {
        if (vis[i] == 0)
            for (int j = i * i; j < N; j += i)
                vis[j] = 1;
    }
    for (int i = 2, t = 0; i < N; ++i)
        if (!vis[i]) prime[++num] = i;
}

int main()
{
    initPrime(); char c;
    while (scanf ("%d", &a), a)
    {
        scanf ("%d%c", &b, &c);
        x = pow (a*1.0, b);
        while (c == ' ')
        {
            scanf ("%d %d%c", &a, &b, &c);
            x = x * pow (a*1.0, b);
        }
        --x; last = 0;
        memset(ans,0,sizeof(ans));

        for (int i = 1; x > 1; m=i,++i)
            if (x % prime[i] == 0)
            {
                if (!last) last = i;
                while (x % prime[i] == 0)
                {
                    ++ans[i];
                    x /= prime[i];
                }
            }
        for (int i = m; i >= last; --i)
            if (ans[i]) printf (i == last ? "%d %d\n" : "%d %d ", prime[i], ans[i]);
    }
    return 0;
}