记录编号 |
144836 |
评测结果 |
AAAAAAAAAA |
题目名称 |
超强的乘法问题 |
最终得分 |
100 |
用户昵称 |
Asm.Def |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.700 s |
提交时间 |
2014-12-29 23:23:07 |
内存使用 |
20.16 MiB |
显示代码纯文本
/*====================Asm.Def========================*/
#include <iostream>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cmath>
using namespace std;
typedef unsigned long long LL;
typedef unsigned uint;
/*======================================================*/
const uint maxn = 524288, E = 18702539, p = 104857601;
inline uint powmod(uint a, uint n){
uint ans = 1;
while(n){if(n & 1)ans = (LL)ans * a % p;a = (LL)a * a % p;n >>= 1;}
return ans;
}
inline uint inv(uint x){return powmod(x, p-2);}
uint A[maxn+5], B[maxn+5];
namespace NTT{
uint e, N, po;
uint rev[maxn+5];
inline void init(uint len){
N = 1;po = 0;
while(N <= len)
++po, N <<= 1;
e = powmod(E, maxn >> po);
}
inline void GetReverse(){
static uint i, j = N >> 1, it1, it2;
for(i = 1,it1 = j;i < N;++i){
if(i < it1)rev[i] = it1, rev[it1] = i;
for(it2 = j;it2 & it1;it2 >>= 1)it1 ^= it2;
it1 ^= it2;
}
}
inline void DNTT(uint *a, uint x){
static uint w2[20], i, j, k, t;
for(i = 0;i < N;++i)if(rev[i] > i)swap(a[i], a[rev[i]]);
w2[0] = x;//w2[i] = x ^ 2 ^ i
for(i = 1;i < po;++i)w2[i] = (LL)w2[i-1] * w2[i-1] % p;
i = po-1,j = 1,k = 2;
do{
for(uint it = 0;it < N;it += k){
static uint X;X = 1;
for(uint it2 = 0;it2 < j;++it2){
t = (LL)a[it+it2+j] * X % p;
a[it+it2+j] = (a[it+it2] + p - t) % p;
a[it+it2] = (a[it+it2] + t) % p;
X = (LL)X * w2[i] % p;
}
}
j <<= 1, k <<= 1;
}while(i--);
}
inline void multi(uint *a, uint *b){
GetReverse();
DNTT(a, e);
DNTT(b, e);
for(uint i = 0;i < N;++i)a[i] = (LL)a[i] * b[i] % p;
DNTT(a, inv(e));
uint t = inv(N);
for(uint i = 0;i < N;++i)a[i] = (LL)a[i] * t % p;
}
}
inline void getpoly(uint *a, uint &len){
static char tmpc[maxn+5];
len = 0;
while(!isdigit(tmpc[len] = getchar())); ++len;
while(isdigit(tmpc[len] = getchar()))++len;
for(int i = len-1, j = 0;i >= 0;--i, ++j)
a[j] = tmpc[i] - '0';
}
/*namespace GetC{
uint g = 3, k, N = maxn;
inline bool isp(){
uint t = (int)(sqrt(p) + 1);
for(uint i = 2;i <= t;++i)
if(p % i == 0)return 0;
return 1;
}
inline bool check(){
for(uint i = 1,a = g;i < p-1;++i, a = a * g % p)
if(a == 1)return 0;
return 1;
}
inline void get(){
for(k = 200,p = k * N + 1;;p += N,++k){
if(!isp())continue;
if(check()){
printf("\nconst uint E = %d, p = %d;", E = powmod(g, k), p);
return;
}
}
}
}*/
int main(){
#if defined DEBUG
freopen("test", "r", stdin);
//freopen("output.txt", "w", stdout);
#else
freopen("bettermul.in", "r", stdin);
freopen("bettermul.out", "w", stdout);
#endif
/*GetC::get();*/
uint lenA, lenB;
getpoly(A, lenA), getpoly(B, lenB);
lenA += lenB;
NTT::init(lenA);
NTT::multi(A, B);
static int i, mor;
for(i = 0;i < (int)lenA;++i){
mor += A[i];
A[i] = mor % 10;
mor /= 10;
}
i = lenA + 1;
while(!A[i])--i;
while(i >= 0)putchar(A[i--] + '0');
#if defined DEBUG
cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
#endif
return 0;
}