记录编号 144836 评测结果 AAAAAAAAAA
题目名称 超强的乘法问题 最终得分 100
用户昵称 GravatarAsm.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;
}