网易Java研发笔试题
网易其中一道笔试题，需要优化到O(n)，可以通过枚举我们的除数从 k加1 到n，求各个余数的满足情况的数目，加起来就是总数了。
我这里用factor 表示 最大因子，比如说输入 （n,k）=（8,2） 当我们除数 i = k+1时， factor = (8 - 2) / i = 1
最大因子表示 n >= factor * i+k 始终成立。
package test;
public class getNum {
static int getNum1(int n,int k){
int sum = 0;
for(int i = k;i <= n;i++){
for(int j = k;j <= n;j++){
if(i % j >= k){
sum++;
}
}
}
return sum;
}
static int getNum2(int n,int k){
int sum = 0;
for(int i = k+1; i <= n; i++){
int factor = (n - k) / i;
if(factor > 0){
sum += factor * (i - k);
sum += Math.min(n,factor * i + (i - 1)) - factor * i - k + 1;
}else{
sum += (i - k);
}
}
return sum;
}
public static void main(String[] args){
int Time = 500000;
for(int i = 0;i < Time;i++){
int k = (int)(Math.random() * 5 + 1);
int n = 20 * k;
if(getNum1(n,k) != getNum2(n,k)){
System.out.println("***");
//break;
}
}
}
}
#春招##实习##笔试题目##网易##Java#
