题目链接
题面
题意
首先定义对于(k)的好数(u)：如果(uleq k)且(u)的所有质因子与(k)的质因子一样则称(u)对于(k)是一个好数。
现给你两个数(k1,k2(1leq k1,k2leq 10^{24}))，要你求(k1,k2)的好数个数，对于(k1,k2)有两者的最大质因子一定相同第二大质因子一定不同。
思路
我们知道对于小于等于(10^{24})的数最多有三个大于(10^6)的质因子，因此对于数(k1,k2)我们可以先将其小于等于(10^6)的质因子全部分离出来，那么最后最多还剩三个质因子的指数相乘。
我们设(p1,p2,p3)为二者的最一、二、三大质因子。
如果最后剩余的(k1,k2)只剩(p1)，那么就只能是(p1)的幂次，此时可以通过枚举求出(p1)的指数，因为大于(1e6)的数最多(3)次就大于(10^{24})了。
如果最后剩余的(k1,k2)剩(p1,p2)的幂次相乘，那么(gcd(k1,k2))一定是(p1)的幂次，因为二者的(p2)一定不同嘛~这样我们可以通过两次枚举得到其指数。
如果最后剩余的(k1,k2)剩(p1,p2,p3)的幂次相乘，那么(p1,p2,p3)的指数一定都是(1)次。
因为好数的要求是需要质因子与(k)相同，所以每个质因子的次数至少为(1)，所以如果(k=p_1^{c_1}p_2^{c_2}dots)，那么答案就是(prodlimits_{i=1}^{n}c_i)。
代码实现如下
import java.util.*;
import java.math.*;
public class Main {
static int cnt = 0;
static Boolean v[] = new Boolean[1000007];
static int p[] = new int[1000007];
public static void init() {
for(int i = 0; i <= 1000000; ++i) v[i] = false;
for(int i = 2; i <= 1000000; ++i) {
if(!v[i]) p[cnt++] = i;
for(int j = 0; j < cnt && i * p[j] <= 1000000; ++j) {
v[i*p[j]] = true;
if(i % p[j] == 0) break;
}
}
}
public static int check(BigInteger k) {
if (k.equals(BigInteger.ONE)) return 1;
BigInteger a = BigInteger.valueOf((long)Math.sqrt(k.doubleValue()));
if (k.equals(a.multiply(a))) return 2;
a = a.add(BigInteger.ONE);
if (k.equals(a.multiply(a))) return 2;
BigInteger b = BigInteger.valueOf((long)Math.pow(k.doubleValue(), 1.0/3));
if (k.equals(b.multiply(b.multiply(b)))) return 3;
b = b.add(BigInteger.ONE);
if (k.equals(b.multiply(b.multiply(b)))) return 3;
return 1;
}
public static void main(String[] args) {
init();
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
BigInteger k[] = new BigInteger[5];
while(t-- != 0) {
for(int i = 0; i < 2; ++i) k[i] = sc.nextBigInteger();
long ans[] = new long[5];
for(int i = 0; i < 2; ++i) {
ans[i] = 1L;
for(int j = 0; j < cnt; ++j) {
if(k[i].mod(BigInteger.valueOf(p[j])) == BigInteger.ZERO) {
long num = 0;
while(k[i].mod(BigInteger.valueOf(p[j])) == BigInteger.ZERO) {
++num;
k[i] = k[i].divide(BigInteger.valueOf(p[j]));
}
ans[i] *= num;
}
}
}
k[2] = k[0].gcd(k[1]);
if(k[2].compareTo(BigInteger.valueOf(1000000)) > 0) {
int x = check(k[2]);
BigInteger g;
if(x == 1) g = k[2];
else if(x == 2) {
BigInteger tmp = BigInteger.valueOf((long)Math.sqrt(k[2].doubleValue()));
if(k[2].equals(tmp.multiply(tmp))) g = tmp;
else g = tmp.add(BigInteger.ONE);
} else {
BigInteger tmp = BigInteger.valueOf((long)Math.pow(k[2].doubleValue(), 1.0/3));
if(k[2].equals(tmp.multiply(tmp).multiply(tmp))) g = tmp;
else g = tmp.add(BigInteger.ONE);
}
for(int i = 0; i < 2; ++i) {
long num = 0;
while(k[i].mod(g) == BigInteger.ZERO) {
++num;
k[i] = k[i].divide(g);
}
ans[i] *= num;
if(k[i].compareTo(BigInteger.valueOf(1000000)) > 0) {
ans[i] *= check(k[i]);
}
}
}
System.out.println(ans[0] + " " + ans[1]);
}
sc.close();
}
}
对象用(=)进行比较是否相等是看地址。
