C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 588K, 提交时间: 2020-06-02 09:38:54

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int n=20200524,m=24;
const int a[31]={1,2,3,4,6,12,1123,1499,2246,2998,3369,4492,4497,5996,6738,8994,13476,
17988,1683377,3366754,5050131,6733508,10100262,20200524};
int b[31];
int main(){
    int t,x,y;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&x,&y);
        for(int i=0;i<m;i++) b[i]=x/a[i];
        for(int i=m-1;i>=0;i--)
            for(int j=i+1;j<m;j++)
                if(a[j]%a[i]==0) b[i]-=b[j];
        ll ans=0;
        for(int i=0;i<m;i++) ans+=1ll*b[i]*(y/(n/a[i]));
        printf("%lld\n",ans);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 492K, 提交时间: 2020-06-30 22:59:57

#include<bits/stdc++.h>
using namespace std;

const int num=20200524;
int main()
{
    int i,j,n,m,T,L=0,a[105],V[105];
    long long ans;
    for(i=1;i*i<num;i++)if(num%i==0)a[L++]=i,a[L++]=num/i;
    sort(a,a+L);
    scanf("%d",&T);
    while(T--)
    {
    	scanf("%d%d",&n,&m),ans=0;
		for(i=0;i<L;i++)V[i]=n/a[i];
    	for(i=L-1;i>=0;i--)
    	    for(j=i+1;j<L;j++)if(a[j]%a[i]==0)V[i]-=V[j];
    	for(i=0;i<L;i++)j=num/a[i],ans+=(long long)V[i]*(m/j);
    	printf("%lld\n",ans); 
	}
    return 0;
}