HDU3988-Harry Potter and the Hide Story(数论-质因数分解)

时间:2022-09-08 22:47:06

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

Problem Description
iSea is tired of writing the story of Harry Potter, so, lucky you, solving the following problem is enough.

HDU3988-Harry Potter and the Hide Story(数论-质因数分解)

 
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
 
题意:给你n和k,让你求出最大的i 满足n的阶乘能被k的i次方整除。

思路:对k进行质因数分解。求出每一个质因数在阶乘中的幂的大小。答案即为最小的那个幂。

#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(数论-质因数分解)的更多相关文章

  1. UVA 10892 LCM Cardinality(数论 质因数分解)

    LCM Cardinality Input: Standard Input Output: Standard Output Time Limit: 2 Seconds A pair of number ...

  2. 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 ...

  3. Harry Potter and the Hide Story&lpar;hdu3988&rpar;

    Harry Potter and the Hide Story Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/65536 ...

  4. 数学概念——J - 数论,质因数分解

    J - 数论,质因数分解 Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u Submit ...

  5. 简单数论之整除&amp&semi;质因数分解&amp&semi;唯一分解定理

    [整除] 若a被b整除,即a是b的倍数,那么记作b|a("|"是整除符号),读作"b整除a"或"a能被b整除".b叫做a的约数(或因数),a ...

  6. Pairs Forming LCM (LightOJ - 1236)【简单数论】【质因数分解】【算术基本定理】&lpar;未完成&rpar;

    Pairs Forming LCM (LightOJ - 1236)[简单数论][质因数分解][算术基本定理](未完成) 标签: 入门讲座题解 数论 题目描述 Find the result of t ...

  7. Leetcode 263 Ugly Number 数论 类似质因数分解

    Ugly Number的质因数仅为2,3,5 将输入的数分别除以2,3,5直到不能除,看是否为1,为1的是Ugly Number,其他则不是. class Solution { public: boo ...

  8. hdu 5108&lpar;数论-整数分解&rpar;

    Alexandra and Prime Numbers Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (J ...

  9. 集训第六周 数学概念与方法 J题 数论,质因数分解

    Description Tomorrow is contest day, Are you all ready? We have been training for 45 days, and all g ...

随机推荐

  1. Cannot change version of project facet Dynamic Web Module to 3&period;1

    最近项目一直报错,看的极度的不爽,于是找了很长时间的解决方案. 先说一下环境Spring + SpringMVC + MAVEN + jdk 1.8 + servlet 3.1 由于是web 项目,这 ...

  2. id 和 instancetype

    静态数据类型 默认情况下所有的数据类型都是静态数据类型 静态数据类型的特点: 1 在编译时就知道变量的类型 2 知道变量中有哪些属性和方法 3 在编译的时候就可以访问这些属性和方法 4 并且如果是通过 ...

  3. What&&num;39&semi;s the difference between all the Selection Segues

    relationship -A "relationship" segue is the segue between a container view controller and ...

  4. Back to Basics&colon; Using KVO

    One of the things I like most about Apple’s iOS SDK is the consistent and easy-to-use API they provi ...

  5. Kotlin尝试之一:写代码前的准备

    Kotlin是一种静态类型的编程语言,可在Java虚拟机上运行,也可以编译为JavaScript源代码. 其主要发展来自位于俄罗斯圣彼得堡的JetBrains程序员团队. 虽然语法与Java不兼容,但 ...

  6. html5 文本格式化

    通常标签 <strong> 替换加粗标签 <b> 来使用, <em> 替换 <i>标签使用.然而,这些标签的含义是不同的:<b> 与< ...

  7. Python第3次作业--李珠霞

    习题1: **1.初始化一个数据集,包括5-10位同学的成绩数据(数据类型不限),数据格式如下: **学号 姓名 Java C语言 Python2017XXXX 小白 87 68 922017XXXX ...

  8. 命令行下执行python找不包的解决方法

    首先我们来了解一下,为什么会出现这样的问题,以及python搜索包的机制是怎么样的 1.为什么会出现这样的问题? 包是向下搜索机制. 2.为什么ide中执行没有报找不到包的问题? python搜索机制 ...

  9. dubbo-2&period;5&period;6优雅停机研究

    不优雅的停机: 当进程存在正在运行的线程时,如果直接执行kill -9 pid时,那么这个正在执行的线程被中断,就好像一个机器运行中突然遭遇断电的情况,所导致的结果是造成服务调用的消费端报错,也有可能 ...

  10. boost 实现http断点续传

    // testc.cpp : Defines the entry point for the console application. // #include "stdafx.h" ...