注意到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());
    }
}