#2042. 挑战分解质因数

    ID: 2042 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest763来源:qoj.ac数据:公开样例高精度数论

挑战分解质因数

挑战分解质因数

题目描述

标题: 挑战分解质因数 - Problem - QOJ.ac

#4920. 挑战分解质因数

Statistics

The problem was used in the following contests:

一天,小 Δ 给你了一个张纸,上面写了一个很大的数字 n ,他想让你在一秒钟内对它分解质因数,你定睛一看,发现这个数的二进制有高达 1500 位,然后你上网搜索了一下,发现连 RSA-1024 都还没有被分解出来,怎么可能一秒分出来呢?

但是突然你发现他在纸的背面也写了一些东西,你又定睛一看发现写的是 φ(n),也就是 ≤n 的且与 n 互质的正整数个数。

这下你好像明白咋分解了,现在你打开了你的电脑,复制出了你的祖传高精度整数运算库,你能一秒钟把结果告诉小 Δ 吗?

输入格式

一行,两个二进制整数 n,φ(n)。

输出格式

如果 n 可以表示为 n=∏i=1Tpi,其中 pi 是质数,且 ∀1≤i<T,pi≤pi+1,那么首先输出一行,包含一个十进制非负整数 T,接下来 T 行,每行一个二进制整数,代表 pi,可以证明这样的表示是唯一的。

样例数据

样例 1 输入

11111101 11011100

样例 1 输出

2
1011
10111

样例 2

见下发文件。

子任务

对于所有数据, 1≤n<21500。

本题采用捆绑测试,子任务如下:

  1. n<232 (5分)
  2. n<264 (15分)
  3. n<2300,n=pq,其中 p,q 为不同的质数 (10分)
  4. n<2300,n=∏i=1Tpi,其中 pi 为两两不同的质数,且 pi≡3(mod4) (15分)
  5. n<2300,n=∏i=1Tpi,其中 pi 为两两不同的质数 (15分)
  6. n<2300 (25分)
  7. 无特殊限制 (15分)

保证每个子任务不超过15个测试点,但子任务之间会设置所有可行的依赖关系。

高精度库

我们在下发文件中提供了题面中提到的“祖传高精度整数运算库”,可以详见下发文件中的文档。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

11111101 11011100
2
1011
10111

样例 2

100111001111011011100001110001100101000101110100101001110011110110000001000100110010100010110001000000010011010001 100111001111011011100001101000100100100011111110011100011000100001110110000101101010001010011011100000010000000000
4
1001101000111100011111010111
10010110011110100001101101101
10011111011011010101111010011
101100011110110101010001000001