拓歐模板
int exgcd(int a, int b, int& x, int& y)
{
if(!b)
{
x=1; y=0; return a;
}
int d = exgcd(b, a%b, y, x);
y-=a/b*x;
return d;
}
歐拉函數
```c++
void euler(int n)
{
for(int i=2; i<=n; i++) phi[i]=i;
for(int i=2; i<=n; i++)
if(phi[i]==i) for(int j=i; j<=n; j+=i) phi[j] = phi[j] /i *(i-1);
}
