题解【CF1444A Division】

题面

t 组数据。
给定参数 p,q，求一个最大的 x，满足 \((x|p)∧(q∤x)\)。
\(1\le t \le 500\)，\(1\le p \le10^{18}\)，\(2\le q\le10^9\),
\(1S\)，\(512MB\)。

思路

当 \(p < q\) 时或 \(q∤p\),答案显然是 \(p\)，直接输出即可
当 \(q | p\)，即 \(q\) 是 \(p\) 的因子时
我们可以将 \(p\) , \(q\) 质因数分解，让 \(p\) 去除以 \(q\)的质因子，直到 \(p\) 不能被 \(q\) 整除，
\(p\) 中比 \(q\) 大的质因子是对上面没有影响的，因此仅考虑\(q\) 的质因子
相比于删除多种质因子，只删一种的方案更优
穷举删除，找到最大值即可
复杂度\(O\) (\(t \sqrt{q}\))

推论

分解质因数 \(p,q,x\)

\[p=\prod a_i^{b_1}
\]

\[q=\prod a_i^{b_2}
\]

\[x=\prod a_i^{b_3}
\]
因为条件是 \((x|p)∧(q∤x)\) 即:

\[p = k \times x =k\times \prod a_i^{b_3}(k\in N^*)
\]

\[∃a_i|q,b_3<b_2
\]
换句话说, \(x\) 中的包含 \(q\) 中的质因子，且质因子数量 \(<q\),可以为 \(0\)
因此要找的 \(x\) 就是 \(p\) 中删除部分质因子后的数，使得达到上述条件
相比删除多种，只需使一种质因子数量不满足上述条件即可，即只删一种
枚举 \(q\) 的所有质因子计算即可

Code

#include <iostream>//声明：luckyblock的思路

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <cmath>

#define int long long //我用 int 来代替 long long

using namespace std;

const int manx=1e6+10;

const int mamx = 1e6 + 11;

const int B = 1e6 + 11;

const int mod = 1e9 + 7;

const int inf = 0x3f3f3f3f;

inline int read() {

  char c = getchar(); int x = 0, f = 1;

  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;

  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);

  return x * f;

}

signed main(){

	int t = read();

	while(t--){

		int ans = 1;

		int  p = read(),q = read();//看清上边备注，和数据范围

		int s = p;

		if(p < q){cout<<p<<endl;continue;}

		if(p % q != 0){cout<<p<<endl;continue;}

		for(int i = 2;i*i <= q; i++){//枚举q中每一个“因子”

			if(q%i == 0){

				int jsq = 0,jsp = 0;

				while(q % i == 0ll){ // 取模最好类型相同

					q = q / i;

					jsq ++;

				}

				while(p % i == 0ll){

					p /= i;

					jsp ++;

				}

				if(jsp < jsq) continue;//说明该 “因子 ”非 “质因子 ”

				int jj =  s;//因为 q p 时刻都在更新，所以预处理 用其他变量代替。

				for(int k = 1; k <=jsp - jsq + 1;k++){

					jj /= i;

				}

				ans = max(jj,ans);

			}

		}

		if(q != 1){//比q大的质因子，注：此时的p q 以被更新，所存的数中不存在共同的质因子

			int jsp = 0;

			while(p % q == 0){

				p /= q;

				jsp++;

			}

			int jj = s;

			for(int i = 1; i <= jsp;i ++){

				jj /= q;

			}

			//cout<<jj<<endl;

			ans = max(jj,ans);

		}

		cout<<ans<<endl;

	}

	return 0;

}

巴特西

题解【CF1444A Division】

题面

思路

推论

Code

最新文章

热门文章