HDU 3988 Harry Potter and the Hide Story(数论-整数和素数)
The and HDU 整数 素数 数论 Hide
2023-09-14 09:10:19 时间
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
Recommend
给定 n和k , 求 n! % k^i 等于0时,i 的最大取值是多少?
解题思路:
将 k分解质因素。n也依据k的质因素求出关系限制i,最后算出最大的i就可以。
解题代码:
#include <iostream> #include <cstdio> #include <map> #include <vector> #include <cstring> using namespace std; typedef unsigned long long ll; ll n,k; const int maxn=10000010; bool isPrime[maxn]; vector <ll> v; ll tol; void get_prime(){ tol=0; memset(isPrime,true,sizeof(isPrime)); for(ll i=2;i<maxn;i++){ if(isPrime[i]){ tol++; v.push_back(i); } for(ll j=0;j<tol && i*v[j]<maxn;j++){ isPrime[i*v[j]]=false; if(i%v[j]==0) break; } } //for(ll i=v.size()-1;i>=v.size()-100;i--) cout<<v[i]<<endl; } map <ll,ll> getPrime(ll x){ map <ll,ll> mp; for(ll i=0;i<tol && x>=v[i];i++){ while(x>0 && x%v[i]==0){ x/=v[i]; mp[v[i]]++; } } if(x>1) mp[x]++; return mp; } void solve(){ if(k==1){ printf("inf\n"); return; } map <ll,ll> mp=getPrime(k); ll ans=1e19; for(map <ll,ll>::iterator it=mp.begin();it!=mp.end();it++){ ll tmp=n,sum=0; while(tmp>0){ sum+=tmp/(it->first); tmp/=(it->first); } if(sum/(it->second)<ans) ans=sum/(it->second); } cout<<ans<<endl; } int main(){ get_prime(); int t; scanf("%d",&t); for(int i=0;i<t;i++){ cin>>n>>k; printf("Case %d: ",i+1); solve(); } return 0; }
版权声明:本文博客原创文章。博客,未经同意,不得转载。
相关文章
- [Kotlin] Adding the Hibernate dependencies to our project and creating the database
- [React] Use React.ReactNode for the children prop in React TypeScript components and Render Props
- [Nuxt] Setup a "Hello World" Server-Rendered Vue.js Application with the Vue-CLI and Nuxt
- [Node.js] Level 1 new. Intro the Node.js
- [Functional Programming] Combine State Dependent Transactions with the State ADT (composeK to replace multi chian call)
- [AngularJS] Store the entry url and redirect to entry url after Logged in
- [RxJS] AsyncSubject and ReplaySubject - Learn the Differences
- [Python] The get() method on Python dicts and its "default" arg
- [Angular] Protect The Session Id with https and http only
- [React Intl] Install and Configure the Entry Point of react-intl
- [Angular] Bind async requests in your Angular template with the async pipe and the "as" keyword
- [SCSS] Organize Styles with SCSS Nesting and the Parent Selector
- [Ramda] Pluck & Props: Get the prop(s) from object array
- [Regular Expressions] Match the Start and End of a Line
- [Node.js]30. Level 6: Listen 'Question' from client, and then Answer the Question
- how is SAP UI5 extension component being loaded in the runtime
- The compiler compliance specified is 11 but a JRE 1.8 is used
- VM启动报错Cannot open the disk,Failed to lock the file
- 【Codeforces 682C】Alyona and the Tree
- 【Educational Codeforces Round 48 (Rated for Div. 2) C】 Vasya And The Mushrooms
- 【23.48%】【codeforces 723C】Polycarp at the Radio
- 【codeforces 768A】Oath of the Night's Watch
- 成功解决VirtualBox is not installed. Please re-run the Toolbox Installer and try again.
- RuntimeError: Input type (torch.cuda.FloatTensor) and weight type (torch.FloatTensor) should be the
- HDUOj Ignatius and the Princess III 题目1002
- 2个问题,解决tomcat启动一闪而过和运行tomcat/bin目录下的startup.bat时报错(the CATALINA_HOME environment variable is not defined correctly)
- 谣言检测——(GLAN)《Jointly embedding the local and global relations of heterogeneous graph for rumor detection》
- 解决办法: Cannot resolve the collation conflict between "Japanese_CI_AS" and "SQL_...