2015
04-14

# 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

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

Recommend
lcy

#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;
}

1. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!