水题挑战6： CF1444A DIvision

• 2020 年 11 月 14 日
• 笔记
• Codeforces, 数学, 水题挑战

A. Division
time limit per test1 second
memory limit per test512 megabytes
inputstandard input
outputstandard output
Oleg’s favorite subjects are History and Math, and his favorite branch of mathematics is division.

To improve his division skills, Oleg came up with \(t\) pairs of integers \(p_i\) and \(q_i\) and for each pair decided to find the greatest integer \(x_i\), such that:

\(p_i\) is divisible by \(x_i\);
\(x_i\) is not divisible by \(q_i\).
Oleg is really good at division and managed to find all the answers quickly, how about you?
Input
The first line contains an integer \(t\) \((1\leq t\leq 50)\) — the number of pairs.

Each of the following \(t\) lines contains two integers \(p_i\) and \(q_i\) (\(1≤p_i≤10^18\); \(2≤q_i≤10^9\)) — the \(i-th\) pair of integers.

Output
Print \(t\) integers: the \(i-th\) integer is the largest \(x_i\) such that \(p_i\) is divisible by \(x_i\), but xi is not divisible by \(q_i\).

One can show that there is always at least one value of xi satisfying the divisibility conditions for the given constraints.

Example
input
3
10 4
12 6
179 822
output
10
4
179

SOLUTION

这还算一道良心数学题

首先我们发现，我们先把p, q质因数分解，有如下结果：

\(p=a_1^{p_1}\times a_2^{p_2}\times … \times a_m^{p_m} \times … a_n^{p_n}\)
\(q=a_1^{q_1}\times a_2^{q_2}\times … \times a_m^{q_m}\)
其中， \(m<n\)

注意，当\(pmodq\ne 0\), 答案就是\(p\)
当\(pmodq=0\)
就是任意小于\(m\)的数\(i\),\(q_i <= p_i\)
于是，我们就只要考虑前\(m\)个质因数
我们只要对于\(p\)的任意一个质因数，\(p_i\)变成\(q_i-1\),就是一个符合条件的答案
求出最大的，我们只需要考虑变化代价最小的计算出来就好了

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define _(d) while(d(isdigit(ch=getchar())))
template <class T> void g(T&t){T x,f=1;char ch;_(!)ch=='-'?f=-1:f;x=ch-48;_()x=x*10+ch-48;t=f*x;}
typedef unsigned long long ll;
const int N = 1e5+4;
int pri[N], tot, vis[N];
ll p,q,ans;
void pre(){
	int End = sqrt(1e9)+1;
	for(int i=2; i <= End; i++){
		if(!vis[i]) pri[++tot]=i;
		for(int j=1; j <= tot; j++){
			if( i*pri[j] > End ) break;
			vis[i*pri[j]] = 1;
			if( i%pri[j] == 0 ) break;
		}
	}
}

int st[N], tp, num1[N], num2[N];
ll s1[N], s2[N];

int main(){
	int T; g(T);
	pre(); 
//	rep(i,1,10) cout<<pri[i]<<endl; 
	while(T--){
	 	g(p), g(q);
	 	if( p%q ) ans = p;
		else{
			tp = 0; ll nowq = q; ans = 0; 
			for( int i=1; pri[i]*pri[i] <= nowq && i<=tot; i++ ){
				if( nowq % pri[i] == 0 ){
					st[++tp] = pri[i]; s1[tp] = 1;
					while( nowq % pri[i] == 0 ){
//						puts("orz");
						nowq /= pri[i];
						s1[tp] *= pri[i];
					}
				}
			}
			if( nowq >1  ) st[++tp] = nowq, s1[tp] = nowq;
			ll nowp = p;
			for( int i=1; i <= tp; i++ ){
				ll tmp = nowp / s1[i]; s2[i] = s1[i];
				while( tmp % st[i] == 0 ){
//					puts("orz");
					s2[i] *= st[i];
					tmp /= st[i];
				}
				nowp = tmp;
			}
			ll mn = 1e18;
			for( int i=1; i <= tp; i++ ){
//				cerr<<s1[i]<<endl;
				s2[i] = s2[i]/s1[i]*st[i]; 
				mn = min( mn, s2[i] );
			}
			ans = p/mn; 
		} 
		printf("%llu\n",ans);
	}
	return 0;
}