学步园

/*<br /> File: 10139.cpp<br /> Author: ACboy<br /> Date: 2010-4-22<br /> Result: AC<br /> Descripition: UVa 10139 Factovisors<br /> */</p> <p>#include <iostream><br /> #include <cmath><br /> #include <set><br /> #include <map><br /> using namespace std;</p> <p>map<long, int> m;<br /> set<long> s;</p> <p>// 求n！中素数p的指数。<br /> int prime_num(long p, long n) {<br /> int num = 0;<br /> for (long i = p; i <= n; i *= p) {<br /> num += n / i;<br /> }<br /> return num;<br /> }</p> <p>// 一个数的素数分解。<br /> void prime_factorization(long a) {<br /> int i;<br /> m.clear();<br /> s.clear();<br /> while (a % 2 == 0) {<br /> if (m.find(2) != m.end()) {<br /> m[2]++;<br /> } else {<br /> m[2] = 1;<br /> s.insert(2);<br /> }<br /> a /= 2;<br /> }<br /> i = 3;<br /> while (i <= (sqrt(double(a)) + 1)) {<br /> if (a % i == 0) {<br /> if (m.find(i) != m.end()) {<br /> m[i]++;<br /> } else {<br /> m[i] = 1;<br /> s.insert(i);<br /> }<br /> a /= i;<br /> } else {<br /> i += 2;<br /> }<br /> }<br /> if (a > 1) {<br /> if (m.find(a) != m.end()) {<br /> m[a]++;<br /> } else {<br /> m[a] = 1;<br /> }<br /> s.insert(a);<br /> }<br /> }</p> <p>int main() {<br /> long long n, M;<br /> #ifndef ONLINE_JUDGE<br /> freopen("10139.txt", "r", stdin);<br /> #endif<br /> while (cin >> n >> M) {<br /> prime_factorization(M);<br /> set<long>::iterator it;<br /> int ok = 1;<br /> for (it = s.begin(); it != s.end(); it++) {<br /> if (prime_num(*it, n) < m[*it]) {<br /> ok = 0;<br /> break;<br /> }<br /> }<br /> if (ok) {<br /> cout << M << " divides " << n << "!" << endl;<br /> } else {<br /> cout << M << " does not divide " << n << "!" << endl;<br /> }<br /> }<br /> return 0;<br /> }</p> <p>