P5435
Maysoul
·
·
题解
这题不就是求 \gcd 嘛！辗转相除法求 \gcd 真是太简单啦！
普通的 \gcd 它长这个样子：
int gcd(int a,int b)
{
if(b==0) return a;
return gcd(b,a%b);
}
然后我们就T飞了。
所以我们有必要引入一种特殊的，好用的，超级快的算法—— Binary GCD 。
Binary GCD （二进制算法求GCD）的思想就是不断的去除因子2以达到降低常数的目的。以下我将详细讲解这种算法：
对于 \gcd(x,y) ，满足 x,y>0 ：
可分以下几种情况：
1. x=y ，显然， \gcd(x,y)=x=y 。
2. x=0 或 y=0 ：
$ y=0$ 时，$ \gcd(x,y)=\gcd(x,0)=x $。
3.$ x,y $ 均为偶数，显然 $ x,y $ 均有因子2，故可以去掉因子2变成：$ \gcd( \frac{x}{2} , \frac{y}{2}) $ 。
4.$ x $ 为奇数，$ y $ 为偶数，则 $ y $ 有因子2，可去掉变成 $ \gcd( x, \frac{y}{2}) $ 。
5.同理，当$ x $ 为偶数，$ y $ 为奇数的时候变成 $ \gcd( \frac{x}{2}, y) $。
6.当$ x,y $ 均为奇数,可得$ \gcd(x,y)= \gcd(x-y,y) $ （$ a \ge b $）。
这玩意叫做**更减相损术**，具体证明过程如下：
当 $ x=y $ 时，$ \gcd(x,y)=x=y $，等同于情况1。
当 $ x>y $ 时，设 $ \gcd(x,y)=a $:
$$\because a \mid x , a \mid y $$
$$\therefore a \mid x-y$$
$$\therefore \gcd(x,y)=\gcd(x-y,y) $$
因为 $ x,y $ 均为奇数，那么 $ x-y $ 是偶数，等同于情况3，可以写为 $ \gcd( \frac{x-y}{2}, y) $。
以上就是二进制算法的全部内容，我们将上面的模拟出来的样式，叫做 **Stein 算法**。
当然模拟的时候使用二进制位运算来大幅提升效率的方式，就是我们所讲的二进制算法了：
```cpp
int gcd(int a,int b)
{
int i,j;
if(a==0) return b;
if(b==0) return a;
for (i=0;0==(a&1);++i) a>>=1;//去掉所有的2
for (j=0;0==(b&1);++j) b>>=1;//去掉所有的2
if(j<i) i=j;
while(1)
{
if(a<b) swap(a,b);//交换a,b
if(0==(a-=b)) return b<<i;//辗转减
while(0==(a&1)) a>>=1;//去掉所有的2
}
return a;
}
```
提交就会发现又T飞了，这是因为我们这个算法一直在循环向下找二进制的末尾0，速度还是太慢。
我们只好再引入一种神器`__builtin `。
以这个开头的函数都是极快的位运算函数，比如我们将要使用的`__builtin_ctz( ) `。
这个函数可以获取到括号内元素中二进制表示的末尾元素0的个数。
利用这个，就可以省去循环跑的时间。
用`__builtin `优化完之后的函数长这样：
```cpp
int gcd(int a,int b)
{
int az=__builtin_ctz(a),bz=__builtin_ctz(b);
int z=min(az,bz);
int dif;
b>>=bz;
while(a)
{
a>>=az;
dif=b-a;
az=__builtin_ctz(dif);
if(a<b) b=a;
if(dif<0) a=-dif;
else a=dif;
}
return b<<z;
}
```
就没有然后了，这题其实根本不用卡常，我什么优化都没加，裸着跑也能跑过。
完整代码放在下方：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
const int mod=998244353;
long long ans,n;
int x[10000];
int y[10000];
int gcd(int a,int b)
{
int az=__builtin_ctz(a),bz=__builtin_ctz(b);
int z=min(az,bz);
int dif;
b>>=bz;
while(a)
{
a>>=az;
dif=b-a;
az=__builtin_ctz(dif);
if(a<b) b=a;
if(dif<0) a=-dif;
else a=dif;
}
return b<<z;
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>x[i];
}
for (int i=1;i<=n;i++)
{
cin>>y[i];
}
for (int i=1;i<=n;i++)
{
ans=0;
long long num=i;//num和ans必须要开long long
for (int j=1;j<=n;j++)
{
ans+=num*gcd(x[i],y[j]);
ans%=mod;//每次计算完之后取一次余避免误差
num=num*i%mod;
}
cout<<ans%mod<<endl;
}
return 0;
}
```