美团后台笔试编程第一题

我靠，这是什么高科技。

暴力只过了90％

对٩(๑^o^๑)۶。。。然而忘记怎么敲了

赛码网时间到了会自动交卷吗

大佬，就不能多给一点提示吗

注意到N只有1000 莫比乌斯可快速求得 1-N和1-M gcd为i的个数 枚举就行了 import java.io.*; import java.util.*; public class Main { static int[]prime=new int[100050]; static boolean[]notp=new boolean[100050]; static int[]mu=new int[100050]; public static void main(String[] args) { FastScanner sc=new FastScanner(); PrintWriter pw=new PrintWriter(System.out); int N=sc.nextInt(); int n=sc.nextInt(); int m=sc.nextInt(); int p=sc.nextInt(); makeMobius(); int[]A=new int[N+1]; A[1]=p; for(int i=2;i<=N;i++){ A[i]=(A[i-1]+153)%p; } long res=0; for(int o=1;o<=N;o++){ long min=Math.min(n,m)/o; long max=Math.max(n,m)/o; long count1=0; long count2=0; for(int i=1;i<=min;i++){ count2+=mu[i]*(min/i)*(max/i); } res+=A[o]*count2; } pw.println(res); pw.flush(); } static int gcd(int a,int b){ return a==0?b:gcd(b%a,a); } static void makeMobius() { Arrays.fill(notp, false); mu[1] = 1; int pnum=0; for (int i = 2; i < 100010; i++) { if (!notp[i]) { prime[++pnum] = i; mu[i] = -1; } for (int j = 1; prime[j]*i < 100010; j++) { notp[prime[j]*i] = true; if (i%prime[j] == 0) { mu[prime[j]*i] = 0; break; } mu[prime[j]*i] = -mu[i]; } } } } class FastScanner{ BufferedReader br; StringTokenizer st; FastScanner(){ br=new BufferedReader(new InputStreamReader(System.in)); st=new StringTokenizer(""); } String nextLine(){ String s=""; try { s=br.readLine(); } catch (IOException e) { e.printStackTrace(); } return s; } boolean hasNext(){ String s = ""; while(!st.hasMoreTokens()){ s=nextLine(); if(s==null)return false; st=new StringTokenizer(s); } return true; } String next(){ String s=""; while(!st.hasMoreTokens()){ s=nextLine(); st=new StringTokenizer(s); } return st.nextToken(); } int nextInt(){ return Integer.valueOf(next()); } long nextLong(){ return Long.valueOf(next()); } double nextDouble(){ return Double.valueOf(next()); } }

求解什么是GCD啊？  我百度了很久都没有出来小白一枚。

只使用普通的欧几里得过90% 

没有优化 通过100%，不过超时了😂