Harry Potter and the Hide Story
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2193 Accepted Submission(s): 530
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
2
2 2
10 10
Case 1: 1
Case 2: 2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std; #define LL unsigned long long const int maxn = 10000005;
bool isPrime[maxn];
vector<LL> prime,digit,cnt; void getPrime(){
prime.clear();
memset(isPrime,0,sizeof isPrime);
for(LL i = 2; i < maxn; i++){
if(!isPrime[i]){
prime.push_back(i);
for(LL j = i*i; j < maxn; j += i)
isPrime[j] = 1;
}
}
} void getDigit(LL k){ for(int i = 0; i < prime.size() && k >= prime[i]; i++){
if(k%prime[i]==0){
int tt = 0;
digit.push_back(prime[i]);
while(k%prime[i]==0){
tt++;
k /= prime[i];
}
cnt.push_back(tt);
}
}
if(k!=1){
digit.push_back(k);
cnt.push_back(1);
}
} LL getSum(LL n,LL p){
LL res = 0;
while(n){
n /= p;
res += n;
}
return res;
}
int main(){
int ncase,T=1;
LL k,n;
getPrime();
cin >> ncase;
while(ncase--){
cin >> n >> k;
if(k==1){
printf("Case %d: inf\n",T++);
continue;
}
LL ans = -1;
digit.clear();
cnt.clear();
getDigit(k); for(int i = 0; i < digit.size(); i++){
LL tk = getSum(n,digit[i])/cnt[i];
if(ans == -1) ans = tk;
else ans = min(ans,tk);
}
printf("Case %d: %I64u\n",T++,ans); }
return 0;
}
版权声明:本文博客原创文章。博客,未经同意,不得转载。
HDU3988-Harry Potter and the Hide Story(数论-质因数分解)的更多相关文章
-
UVA 10892 LCM Cardinality(数论 质因数分解)
LCM Cardinality Input: Standard Input Output: Standard Output Time Limit: 2 Seconds A pair of number ...
-
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 Pott ...
-
Harry Potter and the Hide Story(hdu3988)
Harry Potter and the Hide Story Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 ...
-
数学概念——J - 数论,质因数分解
J - 数论,质因数分解 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit ...
-
简单数论之整除&;质因数分解&;唯一分解定理
[整除] 若a被b整除,即a是b的倍数,那么记作b|a("|"是整除符号),读作"b整除a"或"a能被b整除".b叫做a的约数(或因数),a ...
-
Pairs Forming LCM (LightOJ - 1236)【简单数论】【质因数分解】【算术基本定理】(未完成)
Pairs Forming LCM (LightOJ - 1236)[简单数论][质因数分解][算术基本定理](未完成) 标签: 入门讲座题解 数论 题目描述 Find the result of t ...
-
Leetcode 263 Ugly Number 数论 类似质因数分解
Ugly Number的质因数仅为2,3,5 将输入的数分别除以2,3,5直到不能除,看是否为1,为1的是Ugly Number,其他则不是. class Solution { public: boo ...
-
hdu 5108(数论-整数分解)
Alexandra and Prime Numbers Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (J ...
-
集训第六周 数学概念与方法 J题 数论,质因数分解
Description Tomorrow is contest day, Are you all ready? We have been training for 45 days, and all g ...
随机推荐
-
Cannot change version of project facet Dynamic Web Module to 3.1
最近项目一直报错,看的极度的不爽,于是找了很长时间的解决方案. 先说一下环境Spring + SpringMVC + MAVEN + jdk 1.8 + servlet 3.1 由于是web 项目,这 ...
-
id 和 instancetype
静态数据类型 默认情况下所有的数据类型都是静态数据类型 静态数据类型的特点: 1 在编译时就知道变量的类型 2 知道变量中有哪些属性和方法 3 在编译的时候就可以访问这些属性和方法 4 并且如果是通过 ...
-
What&#39;s the difference between all the Selection Segues
relationship -A "relationship" segue is the segue between a container view controller and ...
-
Back to Basics: Using KVO
One of the things I like most about Apple’s iOS SDK is the consistent and easy-to-use API they provi ...
-
Kotlin尝试之一:写代码前的准备
Kotlin是一种静态类型的编程语言,可在Java虚拟机上运行,也可以编译为JavaScript源代码. 其主要发展来自位于俄罗斯圣彼得堡的JetBrains程序员团队. 虽然语法与Java不兼容,但 ...
-
html5 文本格式化
通常标签 <strong> 替换加粗标签 <b> 来使用, <em> 替换 <i>标签使用.然而,这些标签的含义是不同的:<b> 与< ...
-
Python第3次作业--李珠霞
习题1: **1.初始化一个数据集,包括5-10位同学的成绩数据(数据类型不限),数据格式如下: **学号 姓名 Java C语言 Python2017XXXX 小白 87 68 922017XXXX ...
-
命令行下执行python找不包的解决方法
首先我们来了解一下,为什么会出现这样的问题,以及python搜索包的机制是怎么样的 1.为什么会出现这样的问题? 包是向下搜索机制. 2.为什么ide中执行没有报找不到包的问题? python搜索机制 ...
-
dubbo-2.5.6优雅停机研究
不优雅的停机: 当进程存在正在运行的线程时,如果直接执行kill -9 pid时,那么这个正在执行的线程被中断,就好像一个机器运行中突然遭遇断电的情况,所导致的结果是造成服务调用的消费端报错,也有可能 ...
-
boost 实现http断点续传
// testc.cpp : Defines the entry point for the console application. // #include "stdafx.h" ...