首页 > 代码库 > HDU 3988 Harry Potter and the Hide Story(数论-整数和素数)
HDU 3988 Harry Potter and the Hide Story(数论-整数和素数)
Harry Potter and the Hide Story
Problem Description
iSea is tired of writing the story of Harry Potter, so, lucky you, solving the following problem is enough.
Input
The first line contains a single integer T, indicating the number of test cases.
Each test case contains two integers, N and K.
Technical Specification
1. 1 <= T <= 500
2. 1 <= K <= 1 000 000 000 000 00
3. 1 <= N <= 1 000 000 000 000 000 000
Each test case contains two integers, N and K.
Technical Specification
1. 1 <= T <= 500
2. 1 <= K <= 1 000 000 000 000 00
3. 1 <= N <= 1 000 000 000 000 000 000
Output
For each test case, output the case number first, then the answer, if the answer is bigger than 9 223 372 036 854 775 807, output “inf” (without quote).
Sample Input
2 2 2 10 10
Sample Output
Case 1: 1 Case 2: 2
Author
iSea@WHU
Source
2011 Multi-University Training Contest 15 - Host by WHU
Recommend
lcy
题目大意:
给定n和k, 求 n! 能被 k^i 整除时,i 的最大取值。
解题思路:
将k分解质因素,问题变为,(1×2×3×...×n) 要被 ( p1^(i*a1) × p2^(i*a2) × ... × pn^(i*an) ) 整除,即分子中各分母的质因数的幂次要大于等于分母。
所以根据k的各质因素,求出满足各质因数的幂次 分子>=分母 的关系限制i,算出最大的i即可。
这题要用到unsigned long long,比较坑。。
参考代码:
#include <iostream> #include <cstring> #include <cmath> #define INF 9223372036854775807ULL using namespace std; typedef unsigned long long ull; const int MAXN = 10000010; int T, cnt; ull N, K, ans, factorA[MAXN], factorB[MAXN], totFactor, prime[MAXN], totPrime; bool isPrime[MAXN]; void getPrime(ull n) { memset(isPrime, true, sizeof(isPrime)); totPrime = 0; for (ull i = 2; i <= n; i++) { if (isPrime[i]) { prime[++totPrime] = i; } for (ull j = 1; j <= totPrime && i*prime[j] <= n; j++) { isPrime[i*prime[j]] = false; if (i % prime[j] == 0) break; } } } void getFactor(ull n) { /* ull now = n; totFactor = 0; for (ull i = 2; i*i <= n; i++) { if (now % i == 0) { factorA[++totFactor] = i; factorB[totFactor] = 0; while (now % i == 0) { factorB[totFactor]++; now /= i; } } } if (now != 1) { factorA[++totFactor] = now; factorB[totFactor] = 1; } */ totFactor = 0; ull now = n; for (ull i = 1; i <= totPrime && prime[i] <= now; i++) { if (now % prime[i] == 0) { factorA[++totFactor] = prime[i]; factorB[totFactor] = 0; while (now % prime[i] == 0) { factorB[totFactor]++; now /= prime[i]; } } } if (now != 1) { factorA[++totFactor] = now; factorB[totFactor] = 1; } } void solve() { if (K == 1) { cout << "Case " << ++cnt << ": inf" << endl; } else { getFactor(K); ans = INF; for (ull i = 1; i <= totFactor; i++) { ull temp = N, sum = 0; while (temp > 0) { sum += temp / factorA[i]; temp /= factorA[i]; } if (sum / factorB[i] < ans) { ans = sum / factorB[i]; } } cout << "Case " << ++cnt << ": " << ans << endl; } } int main() { ios::sync_with_stdio(false); cin >> T; getPrime(10000000); while (T--) { cin >> N >> K; solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。