美团笔试编程第二题 - 整除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; } }
#美团#