FFT
<pre><code class="language-cpp">#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1e4+10;
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const double PI=acos(-1.0);
struct comp
{
double x, y;
comp(): x(0), y(0) { }
comp(const double &_x, const double &_y): x(_x), y(_y) { }
};
inline comp operator+(const comp &a, const comp &b) { return comp(a.x + b.x, a.y + b.y); }
inline comp operator-(const comp &a, const comp &b) { return comp(a.x - b.x, a.y - b.y); }
inline comp operator*(const comp &a, const comp &b) { return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
inline comp conj(const comp &a) { return comp(a.x, -a.y); }
int bitrev[maxn + 5];
comp a[maxn], b[maxn], c[maxn];
void FFT(comp *a,int n,int type = 1){
for(int i = 0; i < n; i++)
if(i < bitrev[i]) swap(a[i],a[bitrev[i]]);//求出要迭代的序列
for(int mid = 1; mid < n; mid <<= 1){//待合并区间的中点
comp Wn(cos(PI / mid), type * sin(PI / mid)); //单位根
for(int R = mid << 1, j = 0; j < n; j += R){//R是区间的右端点，j表示前已经到哪个位置了
comp w(1, 0);//幂
for(int k = 0; k < mid; k++, w = w * Wn){//枚举左半部分
comp x = a[j+k], y = w * a[j+mid+k];//蝴蝶效应
a[j+k] = x + y;
a[j+mid+k] = x - y;
}
}
}
if(type == -1){
for(int i = 0; i < n; i++) a[i].x/=n;
}
}
inline void FFT_prepare(int n){
int bits = 0;
while((1 << bits) < n) bits++;
for(int i = 0; i < n; i++) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (bits - 1));
}
int main(){
int na, nb, nc;
while(~scanf("%d%d%d", &na, &nb,&nc)){
int tn = 1;
nb = 2*nb;
nc = 5*nc;
if(na == nb && nb == nc && nc == 0) return 0;
//将最长的那个多项式的次数n进行变换得到tn
while(tn < na + nb + nc+1) tn <<= 1;
FFT_prepare(tn);
//下面对于数组的初始化
for(int i = 0; i < tn; i++) a[i].x = a[i].y=0, b[i].x=b[i].y=0, c[i].x=c[i].y=0;
for(int i = 0; i <= na; i++) a[i].x=1;
for(int i = 0; i <= nb; i++){
if(i%2==0) b[i].x=1;
}
for(int i = 0; i <= nc; i++){
if(i%5==0) c[i].x=1;
}
FFT(a, tn), FFT(b, tn),FFT(c, tn);
for(int i = 0; i < tn; i++) a[i] = a[i] * b[i]*c[i];
FFT(a, tn, -1);
for(int i = 0; i <= na + nb+nc+1; i++){
if((int)(a[i].x+0.5) == 0 || i == na + nb+nc+1){
printf("%d\n", i);
break;
}
}
}
}</code></pre>