美团笔试编程第二题 - 整除7
定义如下结构体
/*
MyNum{
num
*mod7 = num %7;
preFactor = 10^x; ( 10^(x-1) <= num < 10^x)
premod = preFactor %7;
*needAppendTime ；(needAppendTime * premod + mod7)%7 = 0;
}
*/
class MyNum {
public int mod7;
public int needAppendTime;
}
举例分析，对于用例a=1997，b=127；因为127.mod=1，在127填加的数，需要扩大127.preFactor=1000倍，而每增加1000，mod(1000 + 127) = mod( mod(1000 * 1) + mod(127) ) = mod(6 + 1) = 0；所以需要 a.mod = 1。则1997127 % 7 = 0；
========================
127 1996 12
mod 1 1 5
factor 1000 10000 100
fMod 6 4 2
time 1 5 1
则mod = time;
1996-127; 12-1996; 127-12; 1996-12
import java.util.*;
import java.lang.*;
/*
3
127 1996 12
4
*/
public class MeiTuanA {
public static final int MOD = 7;
public static int getCnt(int[] sumRest, MyNum node) {
int ansCnt = sumRest[node.needAppendTime];
if (node.mod7 == node.needAppendTime) {
ansCnt--;
}
return ansCnt;
}
public static int solution(int n, int[] nums) {
MyNum[] nodes = new MyNum[n];
int[] sumRest = new int[MOD];
for (int i = 0; i < n; i++) {
int curNum = nums[i];
int mod7 = curNum % 7;
int pows = (int)(Math.log(nums[i]) / Math.log(10) );
int preFactor = (int) Math.pow(10, pows + 1);
int preFMode7 = preFactor % 7;
int needTime = 0;
while( ( needTime * preFMode7 + mod7) % 7 != 0 ) {
needTime++;
}
nodes[i] = new MyNum(mod7, needTime);
sumRest[mod7]++;
}
int cnt = 0;
for (int i = 0; i < n; i++) {
MyNum curNum = nodes[i];
cnt += getCnt(sumRest, curNum);
}
return cnt;
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = cin.nextInt();
}
System.out.println( solution(n, nums) );
}
}
class MyNum {
public int mod7;
public int needAppendTime;
public MyNum(int mod7, int needAppendTime) {
this.mod7 = mod7;
this.needAppendTime = needAppendTime;
}
}
#美团#
