CF1444ADivision

$Result$

$Hyperlink$

http://codeforces.com/contest/1444/problem/A

$Description$

$T$组数据&＃xff0c;每组数据给定$A,B$&＃xff0c;问满足是$A$的约数但不是$B$的倍数的最大的正整数

数据范围&＃xff1a;T≤50,A≤1018,B≤109T\leq 50,A\leq 10^{18},B\leq 10^9T≤50,A≤1018,B≤109

$Solution$

1. 若$A\&＃61;B$&＃xff0c;答案即为$A$的除去本身的最大约数
2. 若$A<B$&＃xff0c;答案为$A$
3. 若$A>B$&＃xff0c;若$A$不是$B$的倍数答案为$A$
   否则&＃xff0c;对$B$分解质因数&＃xff0c;去除到$A$的该此项小于$B$即可

时间复杂度&＃xff1a;O(TB)O(T\sqrt B)O(TB

​)

$Code$

#include
#include
#include
#include
#define LL long long
using namespace std;int T;
LL a,b,res;
inline LL read()
{LL d&＃61;1,f&＃61;0;char c;while(c&＃61;getchar(),!isdigit(c)) if(c&＃61;&＃61;&＃39;-&＃39;) d&＃61;-1;f&＃61;(f<<3)&＃43;(f<<1)&＃43;c-48;while(c&＃61;getchar(),isdigit(c)) f&＃61;(f<<3)&＃43;(f<<1)&＃43;c-48;return d*f;
}
signed main()
{T&＃61;read();while(T--){a&＃61;read();b&＃61;read();if(a&＃61;&＃61;b){for(register int i&＃61;2;i*i<&＃61;b;i&＃43;&＃43;)if(a%i&＃61;&＃61;0){printf("%lld\n",a/i);goto loop;}puts("1");continue;}if(a>b) {if(a%b!&＃61;0) {printf("%lld\n",a);continue;}LL k&＃61;a/b,B&＃61;b;res&＃61;0;for(register int i&＃61;2;i*i<&＃61;b;i&＃43;&＃43;) if(b%i&＃61;&＃61;0) {LL A&＃61;a,now&＃61;1;int tot1&＃61;0,tot2&＃61;0;while(A%i&＃61;&＃61;0) A/&＃61;i,tot1&＃43;&＃43;;while(b%i&＃61;&＃61;0) b/&＃61;i,tot2&＃43;&＃43;,now*&＃61;i;now/&＃61;i;LL p&＃61;A*now;res&＃61;max(res,p);}if(b!&＃61;1) {while(a%b&＃61;&＃61;0) a/&＃61;b;res&＃61;max(res,a);}printf("%lld\n",res);}else printf("%lld\n",a);loop:;}
}