大家都知道，P1495可通过CRT转化为求解同余方程：
$nx≡1（mod \space m)$ 的最小x。
题解区有的用枚举，有的用exgcd,这里提供一种用欧拉公式的做法。（要用CRT）

求解同余方程，与其相关的一个著名公式是欧拉定理：当n和m互质时，$n^{φ(m)}≡1（mod\space m）$。
可是此定理和我们的同余方程没有一点关系，因此我们要做变形：
把$nx≡1（mod \space m)$ 的左右两边同时乘上$n^{φ(m)-1}$,即得$n^{φ(m)}*x≡n^{φ(m)-1}（mod \space m)$,由于n和m互质（题目中说 $a_i$ 两两互质），所以$n^{φ(m)}≡1（mod \space m）（欧拉公式）$，代回刚才式子，我们惊奇地发现：
$x≡n^{φ(m)-1}（mod \space m)$
这样就能快速求得x了。算φ(m)的方法也很简单：

我们知道，若m是x的倍数，则小于m的数里，有$\frac m x$个数和m不互质（因为他们都有因数x），所以有$\frac {m(x-1)}{x}$个数和n互质。但m不止一个因数，所以推导出
$φ(m)=m*\largeΠ\frac{x_i-1}{x}$,其中$x_i$为m的质因数。

这样就有思路了。

#include<bits/stdc++.h>
#define int long long
#define inr __int128
using namespace std;
int n,res[19],mod[19],mul=1;
inr ans;
int euler(int x){//求φ(x)
	int ans=x;
	for(int i=2;i*i<=x;i++)
		if(x%i==0){//分解质因数
			while(x%i==0) x/=i;
			ans/=i,ans*=(i-1);
		}
	if(x!=1) ans/=x,ans*=(x-1);
	return ans;
}
inr ksm(inr a,int b,int m){//快速幂求n^φ(m)%M
	inr t=1;
  	for(inr y=a;b;b>>=1){
  		if(b&1) t=t*y%m;
    	y=(y*y)%m;
 	}
  	return t;
}
signed main(){
    ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>mod[i]>>res[i];
		mul*=mod[i];
	}
	for(int i=1;i<=n;i++){
		inr oth=mul/mod[i];//n
	    oth=ksm(oth,euler(mod[i]),mul);
		ans=(ans+res[i]*oth)%mul;
	}
	mul=ans;//__int128不能直接输出
	cout<<mul;
}

话说学术版是可以发题解的吧 (违规紫衫)