爱奇艺2018笔试题 SSR(A, B)个数
=====更新2================
看到一大佬的代码，10^5, 10^5 只用了100+ms。思路如下
若一个数num所需的最小数factor，使得num*factor可以被开整根号，则称factor为num的补足。（num 其实等于 sqrt^2 * factor )。
若一个数num所需的最小数factor，使得num*factor可以被开整根号，则称factor为num的补足。（num 其实等于 sqrt^2 * factor )。
记录[1,n] 和 [1,m]中所有数字的 补足，若前者的补足等于后者的补足，这这一对数合法。 所以对于序列[1,n]，我们只需保存需要的补足记录个数。
factor1[i]表示[1,n]中补足为i的数字个数；同理得factor2[i]， 则结果为 Sum( factor1[i] * factor2[i] )，i in [1, max(n,m)].
import java.util.*;
import java.lang.*;
/*
in
3 8
out
5
5000 5000
26544
time: 13
10000 10000
57296
time: 17
100000 100000
714036
time: 146
*/
public class iqiyiA3 {
public static final int MAXN = 100000 + 5;
public static int[] sqrtsNums = new int[MAXN];
public static int countSqrtsNums = 0;
public static boolean[] canSqrts = new boolean[MAXN]; //优化搜索, 记录平方数
public static int[] factor1 = new int[MAXN]; //factor1[i] 表示x的个数, x属于[1,n], 且 x = k^2 * i; //缺少因子i的数字有几个。
public static int[] factor2 = new int[MAXN]; //同上
public static boolean canSqrtsNum(int num) {
int sqrt = (int) Math.sqrt(num);
return sqrt * sqrt == num;
}
public static void initSqrtsNums() {
for (int i = 1; i < MAXN; i++) {
if ( canSqrtsNum(i) ) {
canSqrts[i] = true;
sqrtsNums[countSqrtsNums++] = i;
}
}
}
public static void solution(int n, int m) {
int min = Math.min(n, m);
int max = Math.max(n, m);
initSqrtsNums();
for (int i = 1; i <= min; i++) {
if ( canSqrts[i] ) { //i可开根,则所需因子为1。
factor1[1]++;
continue;
}
int restFacor = i;
for (int j = 1; j < countSqrtsNums; j++) {
if ( sqrtsNums[j] > restFacor ) break;
while( restFacor % sqrtsNums[j] == 0 ) {
restFacor /= sqrtsNums[j];
}
}
factor1[restFacor]++;
}
for (int i = 1; i <= max; i++) {
if ( canSqrts[i] ) { //i可开根,则所需因子为1。
factor2[1]++;
continue;
}
int restFacor = i;
for (int j = 1; j < countSqrtsNums; j++) {
if ( sqrtsNums[j] > restFacor ) break;
while( restFacor % sqrtsNums[j] == 0 ) {
restFacor /= sqrtsNums[j];
}
}
factor2[restFacor]++;
}
int ret = 0;
for (int i = 1; i <= max; i++) {
ret += factor1[i] * factor2[i];
}
System.out.println(ret);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int m = cin.nextInt();
//long startTime = System.currentTimeMillis();
solution(n, m);
//long endTime = System.currentTimeMillis();
//System.out.println("time: " + (endTime - startTime) );
}
}
===========更新1=======
自己本地测试了下，优化版本的代码还没暴力版本快（😂 写那么多都是做的无用功），java Math.sqrt操作应该效率挺高了。
不过暴力版本 n = 1e5, m = 1e5 本地IDE测试大概要38s，题目中时间限制为1s，也不能ac吧。不知道更优版本是咋做的。各路大神指导下。
不过暴力版本 n = 1e5, m = 1e5 本地IDE测试大概要38s，题目中时间限制为1s，也不能ac吧。不知道更优版本是咋做的。各路大神指导下。
暴力版本。
import java.util.*;
import java.lang.*;
/*
in
3 8
out
5
5000 5000
26544
time: 109
100000 100000
637766
time: 38195 ->38 seconds
*/
public class iqiyiA2 {
public static boolean SSRIsInt(int num1, int num2) {
int t = num1 * num2;
int sqrt = (int) Math.sqrt( t );
return sqrt * sqrt == t;
}
public static void solution(int n, int m) {
if (n > m) {
//swap
n = n ^ m;
m = n ^ m; //n^m^m = n
n = n ^ m; //n^m^n = m
}
//System.out.println(n + " " + m);
//init cnt; i=j have n pairs;
int cnt = n;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if ( SSRIsInt(i, j) ) {
cnt += 2;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j <= m; j++) {
if ( SSRIsInt(i, j) ) {
cnt++;
}
}
}
System.out.println(cnt);
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int m = cin.nextInt();
long startTime = System.currentTimeMillis();
solution(n, m);
long endTime = System.currentTimeMillis();
System.out.println("time: " + (endTime - startTime) );
}
} ==原答案=============================
暴力写完，也写好了优化版本，手贱变量1，2写错了，调了好久。。。没赶上时间提交。
原代码太长，贴这里了
#爱奇艺##Java工程师#
三奇智元机器人科技有限公司公司福利 65人发布
