【HDU1402】【FNT版】A * B Problem Plus

Problem Description
Calculate A * B.
 
Input
Each line will contain two integers A and B. Process to end of file.

Note: the length of each integer will not exceed 50000.

 
Output
For each case, output A * B in one line.
Sample Input
1
2
1000
2
Sample Output
2
2000
Author
DOOM III
 
Recommend
DOOM III   |   We have carefully selected several similar problems for you:  1215 1695 1066 1042 1408
【分析】
写个数论变换还被卡出翔....
什么世道啊。。。。
 /*
宋代朱敦儒
《西江月·世事短如春梦》
世事短如春梦,人情薄似秋云。不须计较苦劳心。万事原来有命。
幸遇三杯酒好,况逢一朵花新。片时欢笑且相亲。明日阴晴未定。
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <string>
#include <ctime>
#define LOCAL
const int MAXN = + ;
const long long MOD = (479ll<<21ll) + ;//费马数论变换的费马素数
long long G = ;//元根
using namespace std;
typedef long long ll;
ll x1[MAXN], x2[MAXN];
ll Inv[MAXN], wn[MAXN];
ll Inv2[MAXN];
char a[MAXN], b[MAXN]; ll pow(ll a, ll b){
if (b == ) return % MOD;
if (b == ) return a % MOD;
ll tmp = pow(a, b / );
if (b % == ) return (tmp * tmp) % MOD;
else return ((tmp * tmp) % MOD * (a % MOD)) % MOD;
}
ll exgcd(ll a, ll b, ll &x, ll &y){
if (b == ){x = 1ll; y = ; return a;}
ll tmp = exgcd(b, a % b, y, x);
y -= x * (a / b);
return tmp;
}
ll inv(ll a, ll p){
ll x, y;
ll tmp = exgcd(a, p, x, y);
return ((x % MOD) + MOD) % MOD;
}
void change(ll *x, int len, int loglen){
for (int i = ; i < len; i++){
int t = i, k = , tmp = loglen;
while (tmp--) {k = (k << ) + (t & ); t >>= ;}
if (k < i) swap(x[i], x[k]);
}
return;
}
void FNT(ll *x, int len, int loglen, int type){
if (type) change(x, len, loglen);
int t;
t = (type ? : ( << loglen));
for (int i = ; i < loglen; i++){
if (!type) t >>= ;
int l = , r = l + t;
while (l < len){
ll a, b;
ll tmp = 1ll, w = wn[t] % MOD;
if (!type) w = Inv[t];
for (int j = l; j < l + t; j++){
if (type){
a = x[j] % MOD;
b = (x[j + t] * (tmp % MOD)) % MOD;
x[j] = (a + b) % MOD;
x[j + t] = ((a - b) % MOD + MOD) % MOD;
}else{
a = (x[j] + x[j + t]) % MOD;
b = ((((x[j] - x[j + t]) % MOD + MOD) % MOD) * tmp) % MOD;
x[j] = a;
x[j + t] = b;
}
tmp = (tmp * w) % MOD;
}
l = r + t;
r = l + t;
}
if (type) t <<= ;
}
if (!type){
change(x, len, loglen);
for (int i = ; i < len; i++) x[i] = (x[i] % MOD * Inv2[len]) % MOD;
}
}
int work(char *a, char *b){
int len1, len2, loglen = ;
len1 = strlen(a);
len2 = strlen(b);
while (( << loglen) < (max(len1, len2) << )) loglen++;
for (int i = ; i < len1; i++) x1[i] = 1ll * (a[i] - '');
for (int i = ; i < len2; i++) x2[i] = 1ll * (b[i] - '');
for (int i = len1; i < (<<loglen); i++) x1[i] = ;
for (int i = len2; i < (<<loglen); i++) x2[i] = ;
FNT(x1, (<<loglen), loglen, );
FNT(x2, (<<loglen), loglen, );
for (int i = ; i < (<<loglen); i++) x1[i] = (x1[i] * x2[i]) % MOD;
FNT(x1, (<<loglen), loglen, ); int len;
ll over, t;
over = ;
len = ;
for (int i = (len1 + len2) - ; i >= ; i--){
t = x1[i] + over;
a[len++] = t % ;
over = t / ;
}
while (over){
a[len++] = over % ;
over /= ;
}
return len;
}
void print(char *t, int len){
for (; len >= && !t[len]; len--);
if (len < ) printf("");
else for (int i = len; i >= ; i--) printf("%c", t[i] + '');
printf("\n");
}
void prepare(){
wn[] = MOD - ;
for (int i = ; i < ; i++){
if (i != && (MOD - ) / (i * ) == (MOD - ) / ((i - ) * )){
wn[i] = wn[i - ];
Inv[i] = Inv[i - ];
}else{
wn[i] = pow(G, (MOD - ) / ( * i));
Inv[i] = inv(wn[i], MOD);
}
Inv2[i] = inv(i, MOD);
}
} int main() {
memset(a, , sizeof(a));
memset(b, , sizeof(b));
prepare();
while (scanf("%s%s", a, b) != EOF){
print(a, work(a, b));
memset(a, , sizeof(a));
memset(b, , sizeof(b));
}
return ;
}
上一篇:redis.conf配置详解


下一篇:Genaro Network —— 区块链3.0缔造者