6-JZTXT

Benefit

题意：使得 $\operatorname{lcm}(a,b)=c$ 成立最小的 $b$，若没有满足条件的$ b$，输出 NO SOLUTION。

$1≤t≤10^5，1\le a,c\le 10^7$

题解：

法一：

$\operatorname{lcm} = \dfrac{ab}{\gcd(a,b)} = c$

$\dfrac{b}{\gcd(a,b)} = \dfrac{c}{a}$

$\because \dfrac{b}{\gcd(a,b)}$是整数,那$\dfrac{c}{a}$也要是整数,即若$c\bmod a \neq 0$则输出NO SOLUTION

否则的话我们去找合适的$b$

令$d = \dfrac{c}{a}$，设函数$f(a,d)$为使得$\dfrac{x}{\gcd(a,x)}=d$成立的最小的$x$,再分类讨论:

当$gcd(a,d)=1$时，显然$x = d$
当$\gcd(a,d)>1$时，设$k = \gcd(a,x)$代入$f(a,d)$得$x = kd$

则有$k = \gcd(a,kd)$

设$\gcd(a,d)=g$,则$\frac{k}{g}=\gcd(\frac{a}{g},\frac{d}{g}k)$

$\because \dfrac{a}{g}$和$\dfrac{d}{g}$已经是互质的,则$\frac{k}{g}=\gcd(\frac{a}{g},k)$

移项得:$\frac{k}{gcd(\frac{a}{g},{k})} = g$

通过递归求解$f(\frac{a}{g},g)$求得$k$

最后答案为$x = kd$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
/*
		lcm(a,b) = c;
		a*b/gcd(a,b) = c;
		b/gcd(a,b) = c/a;
		d = c/a;
		f(a,d) = x ==> x/gcd(a,x) = d;
		if(gcd(a,d)==1) x = d;
		else(gcd(a,d)>1)
		{
			设gcd(a,x) = k;
			x = dk;
			gcd(a,dk) = k;
			设gcd(a,d)  = g;
			gcd(a/g,dk/g) = k/g;
			a/g和d/g互质
			所以gcd(a/g,k) = k/g
			k/gcd(a/g,k) = g;
			求f(a/g,g);
		}
*/
int f(int a,int d)
{
	int g = gcd(a,d);
	if(g==1)return 1;
	return f(a/g,g);
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int a,c;
		cin>>a>>c;
	
		if(c%a)cout<<"NO SOLUTION\n";
		else
		{
			int d = c/a;
			cout<<d*f(a,d)<<endl;
		}
	}	
	return 0;
}

法二:我们可以很容易知道答案一定是质数,因为如果是合数那我们一定可以消去一个约数找到更优的。

同样对于每个$a,c$若$c\bmod a \neq 0$则无解，否则

$lcm(a,b) = \dfrac{ab}{\gcd(a,b)}=c$

$\dfrac{b}{\gcd(a,b)} = \dfrac{c}{a}$ ,设$b = \dfrac{c}{a}$,若$\gcd(a,b)\neq 1$就不断调整

理由如下:

令$b = \dfrac{c}{a}$，$d = \gcd(a,b)$,若$\gcd(a,b)\neq 1$,则就证明此时的$a$和$b的最小公倍数$肯定不是$c$,

而是$\dfrac{ab}{d}$,那么我们通过$a = \dfrac{a}{d}和b = b\times d$进行调整，保证了$\dfrac{ab}{gcd(a,b)}=c$仍成立的同时消去一个公因子

不断调整直到$d=1$，输出$b$就是答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
void solve(ll a,ll c)
{
	ll b,d;
	if(c%a)
	{
		cout<<"NO SOLUTION\n";
		return;
	}
	b=c/a;
	d=gcd(a,b);
	while(d!=1)
	{
		a/=d;
		b*=d;
		//保证a*b/gcd(a,b)==c的同时去掉了一个公因子
		d=gcd(a,b);
	}
	cout<<b<<endl;
	return;
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		ll a,c;
		cin>>a>>c;
		// if(c%a)cout<<"NO SOLUTION\n";
		// else
		// {
		// 	ll t = c/a;
		// 	cout<<"t = "<<t<<endl;
		// 	ll g = gcd(t,a);
		// 	cout<<"g = "<<g<<endl;
		// 	cout<<t*g<<endl;
		// }
		solve(a,c);
	}
	return 0;
}

法三:

根据之前 b 为 $\dfrac{c}{a}$ 的倍数就可以循环枚举 $b$ 判断是否满足$ b = \dfrac{c}{a} \times \gcd(a,b)$。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b % a) {printf("NO SOLUTION\n");continue;}
        int x = b / a;
        for(int i = x;i <= b;i += x)
        {
            int gcd = __gcd(a,i);
            if(gcd * x == i) {printf("%d\n",i);break;}
        }
    }   
    return 0;
}