POJ 1365 - Prime Land

http://poj.org/problem?id=1365

概要

\(x = p_{k_x} ^ {e_{k_x}} \cdot p_{k_x-1} ^ {e_{k_x-1}} \cdots p_1 ^ {e_1}\) という形で 整数 \(x\) が与えられるので、\(x-1\) をこのように因数分解した形で答える。

制約

• \(2 < x \le 32767\)

解法

やるだけ。

 1 #include <iostream>
 2 #include <sstream>
 3 #include <vector>
 4 using namespace std;
 5 
 6 int pow(int p, int e)
 7 {
 8   if (e == 0) {
 9     return 1;
10   } else if ((e & 1) == 0) {
11     const int x = pow(p, e>>1);
12     return x*x;
13   } else {
14     return p * pow(p, e-1);
15   }
16 }
17 
18 int main()
19 {
20   for (string s; getline(cin, s) && s != "0";) {
21     int n = 1;
22     {
23       istringstream iss(s);
24       for (int p, e; iss >> p >> e;) {
25         n *= pow(p, e);
26       }
27     }
28     --n;
29 
30     vector<pair<int,int> > v;
31     for (int i = 2; n != 1; i++) {
32       pair<int,int> p(i, 0);
33       while (n % i == 0) {
34         n /= i;
35         ++p.second;
36       }
37       if (p.second != 0) {
38         v.push_back(p);
39       }
40     }
41     if (v.empty()) {
42       cout << "1 1" << endl;
43     } else {
44       for (vector<pair<int,int> >::const_reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
45         if (it != v.rbegin()) {
46           cout << " ";
47         }
48         cout << it->first << " " << it->second;
49       }
50       cout << endl;
51     }
52   }
53   return 0;
54 }