爱奇艺笔试题SSR（java试题，全用c++过，感觉很尴尬）
先筛出1-1e5的平方数
扫1-n区间，记录平方数，并且统计区间内，每个数需要什么因子才可以被开平方
扫1-m区间，记录平方数，并且统计区间内，每个数需要什么因子才可以被开平方
两数平方根的平方，是否是整数，其实就是sqrt(a*b)是否是整数
(sqrt(a)+sqrt(b))² = a+b +2sqrt(a*b)
所以答案便是
a可能的平方数*b可能的平方数
加上 a所需因子与b所需因子相同的数 eg:12（2倍根号3）与27（3倍根号3）所需的因子数都是3
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stack>
using namespace std;
const int maxn = 1e+5 + 10;
int flag1[maxn];
int flag2[maxn];
int flag[maxn];
int sqrtnum[maxn];
int main()
{
int n, m;
cin >> n >> m;
int sqrt1 = 0;
for(int i = 1; i < maxn; ++i)
{
int sqt = sqrt(i);
if(sqt * sqt == i)
{
flag[i] = 1;
sqrtnum[sqrt1++] = i;
}
}
for(int i = 1 ; i <= n ; ++i)
{
if(flag[i] == 1){
flag1[1]++;
continue;
}
int tmp = i;
for(int j = 1 ; j < sqrt1; ++j){
if(sqrtnum[j] > tmp){
break;
}
while(tmp%sqrtnum[j]==0){
tmp/=sqrtnum[j];
}
}
++flag1[tmp];
}
for(int i = 1 ; i <= m ; ++i)
{
if(flag[i] == 1){
flag2[1]++;
continue;
}
int tmp = i;
for(int j = 1 ; j < sqrt1; ++j){
if(sqrtnum[j] > tmp){
break;
}
while(tmp%sqrtnum[j]==0){
tmp/=sqrtnum[j];
}
}
++flag2[tmp];
}
int ans = 0;
for(int i= 1; i <= maxn; ++i)
{
ans += flag1[i] * flag2[i];
}
cout << ans <<endl;
return 0;
}
不会java的弱智程序员
查看14道真题和解析