如何建立外卖网站,网站建设仿站,农产品网站设计,重庆建设厂历史题目链接 传送门 题面 题意 首先定义对于\(k\)的好数\(u\)#xff1a;如果\(u\leq k\)且\(u\)的所有质因子与\(k\)的质因子一样则称\(u\)对于\(k\)是一个好数。 现给你两个数\(k1,k2(1\leq k1,k2\leq 10^{24})\)#xff0c;要你求\(k1,k2\)的好数个数#xff0c;对于\(k1,k2… 题目链接 传送门 题面 题意 首先定义对于\(k\)的好数\(u\)如果\(u\leq k\)且\(u\)的所有质因子与\(k\)的质因子一样则称\(u\)对于\(k\)是一个好数。 现给你两个数\(k1,k2(1\leq k1,k2\leq 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\)所以如果\(kp_1^{c_1}p_2^{c_2}\dots\)那么答案就是\(\prod\limits_{i1}^{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();}
} 对象用\(\)进行比较是否相等是看地址。 转载于:https://www.cnblogs.com/Dillonh/p/11189802.html
