Topic link :

pid=3641"> Portal

The question :

Minimum ( x! ) = 0 mod (a1^b1*a2^b2...an^bn)

analysis :

First of all a1~an Prime factorization , Then count the index of each qualitative factor . Because with x The increase of , The number of prime factors is gradually added

So we were able to split x. Yes x! Prime factorization is used to infer whether the condition is satisfied . And then find the smallest one .

The code is as follows :

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 110;
typedef long long LL;
bool vis[maxn];
int p[maxn],cnt;
LL a[maxn];
LL b[maxn];
LL num[maxn]; void init(){
cnt = 0;
memset(vis,0,sizeof(vis));
for(int i=2;i<maxn;i++){
if(!vis[i]){
p[cnt++]=i;
for(int j=i+i;j<maxn;j+=i)
vis[j]=1;
}
}
} LL get_num(LL x,int pri){
if(x<pri) return 0;
return get_num(x/pri,pri)+(LL)x/pri;
} bool check(LL x){
for(int i=0;i<cnt;i++){
if(get_num(x,p[i])<num[p[i]])
return false;
}
return true;
} int main()
{
init();
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
memset(num,0,sizeof(num));
for(int i=0;i<n;i++){
scanf("%I64d%I64d",a+i,b+i);
int tmp = a[i];
for(int j=0;p[j]*p[j]<=tmp&&j<cnt;j++){
if(tmp%p[j]==0){
LL tot=0;
while(tmp%p[j]==0) tmp=tmp/p[j],tot++;
num[p[j]]+=tot*b[i];
}
}
if(tmp>1) num[tmp]+=b[i];
}
LL ans = 0;
for(int i=0;i<maxn;i++)
ans=max(ans,(LL)i*num[i]);
LL l=0,r=ans;
while(l<=r){
LL mid=(l+r)>>1;
if(check(mid)) r=mid-1;
else l=mid+1;
}
printf("%I64d\n",l);
}
return 0;
}
/*
111
6
6 1000000000000
15 1000000000000
13 1000000000000
7 1000000000000
2 1000000000000
3 1000000000000
*/

HDU 3641 Treasure Hunting( Factorial prime factorization + Two points ) More articles about

  1. hdu 3641 Treasure Hunting Powerful two points

    /** Carelessness : Give a group ai,bi . m = a1^b1 *a2^b2 * a3^ b3 * a4^b4*...*ai^bi Minimum x!%m =0 Ideas : take ai Quality factor decomposition , if x!%m=0 that ...

  2. HDU 3468 Treasure Hunting(BFS+ The largest flow of network flow )

    Title address :HDU 3468 The key to this problem is to think of using network flow . And then think of using bfs To mark the point in the shortest path . First of all, the marking method is , Run once for each assembly point bfs, Record the shortest distance from all points to the point . And then for any pair of starting points , ...

  3. 【 Network flow 】 HDU 3468 Treasure Hunting

    The question : A-Z&&a-z Express Assembly point from A Starting point, passing by The shortest steps Go to the next assembly point (A The next assembly point for B ,Z The next assembly point for a) I met gold on my way (*) You can pick it up ( A point can only be picked up once ) ...

  4. [Codeforces 1201D]Treasure Hunting(DP)

    [Codeforces 1201D]Treasure Hunting(DP) Topic There is one n*m Of the lattice , There are... On the grid k A treasure , A man from (1,1) set out , You can go left or right , But you can't go down . give q Columns , In these columns ...

  5. Codeforces Round #577 (Div. 2) D. Treasure Hunting

    Codeforces Round #577 (Div. 2)  D. Treasure Hunting This one div2 The first three questions are very simple , This D The question is dp It's still more difficult , But the title tells you that you can only go up , therefore ...

  6. hdu 3641 number theory Dichotomy to find the minimum in line with the conditions of miscellaneous mathematical problems

    http://acm.hdu.edu.cn/showproblem.php?pid=3641 Acquire : 1. Dichotomize the minimum value that meets the condition /*================================= ...

  7. hdu3468 Treasure Hunting Binary matching

    // Give me a n*m Graph //. In the blank //* It means there is gold //# Represents a wall // One has to follow the law A...Z..a..z In the order of the shortest path to the next // Every time, he can only take a piece of gold from the place he passes by // You can ask at most ...

  8. Treasure Hunting HDU - 3468

    The question : Enter a n That's ok m Column graph Take the shortest path in alphabetical order at a time , From one letter to the next , Only one gold can be taken , Find the maximum amount of gold you can get after walking through all the letters in the current picture analysis : bfs Find the shortest path For a gold if d ...

  9. (hdu)5652 India and China Origins Two points +dfs

    Topic link :http://acm.split.hdu.edu.cn/showproblem.php?pid=5652 Problem Description A long time ago there ...

Random recommendation

  1. Discuz! X Forum upload attachment to 100% The reason and solution of automatically canceling upload

    Recently received feedback from some webmasters , Say forum upload attachment , To 100% I canceled the upload when I was in . It is found that the index table is attached pre_forum_attachment Tabular aid There's a problem with field self increment , That causes the program logic to return aid The value is actually one My ...

  2. modify apache 2.4.6 Of MPM Pattern

    Edit profile /etc/httpd/conf.modules.d/00-mpm.conf #Select the MPM module which should be used by uncomment ...

  3. kendoui treeview grid spreadsheet

    treeview Stupid way to get id <!DOCTYPE html> <html> <head> <title>API</title> < ...

  4. struts2 Simple file upload in

    2016-08-31 One .       Upload files utilize commons-fileupload-1.2.1.jar Achieve simple upload file , First fill out the form on the page , Remember to add enctype="multip ...

  5. CODEVS1001 A comfortable route ( Union checking set )

    Sort all edges from large to small , Enumerate the largest edges ,O(m) verification , Use and check the set to maintain whether the graph is connected . program CODEVS1001; ; maxn=; INF=; type arr=record u,v,w:int64; ...

  6. 【MyBatis Learning notes 】

    [MyBatis Learning notes ] The first part of the series :ant Download and install of [MyBatis Learning notes ] The second part of the series :ant Introductory example [MyBatis Learning notes ] One of series :MyBatis Introductory example [MyBatis Study ...

  7. css Naming and sorting

    .container { width: 720px; background: #fafafa; border: 2px dashed #999; padding: 10px; float: left ...

  8. Wrong topic ——this The direction of

    Delay or not ,setTimeout Inside function It's all isolated , It doesn't belong to any object , therefore this It will only point to the overall situation

  9. iOS Null type string conversion in network request

    Create a utility class ,   .h: #import <Foundation/Foundation.h> @interface MySetNullWithStrTool : NSObject +( ...

  10. HTTP Request header and its function turn

    HTTP Request header Header And its function Here's an interview URL,http://www.hzau.edu.cn One of the header, The function and function of each part are analyzed according to examples . 1.Accept, The browser side can handle the internal ...