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

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

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

- 【 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 ) ...

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

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

- 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 /*================================= ...

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

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

- (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

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

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

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

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

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

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

- css Naming and sorting
.container { width: 720px; background: #fafafa; border: 2px dashed #999; padding: 10px; float: left ...

- 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

- iOS Null type string conversion in network request
Create a utility class , .h: #import <Foundation/Foundation.h> @interface MySetNullWithStrTool : NSObject +( ...

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