#P4678. Hdu5403 Goldbach

    ID: 3813 传统题 4000ms 64MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-数论线性同余方程扩展欧几里得算法模逆元最小公倍数埃氏筛试除法分解质因数枚举与搜索暴力枚举实用数判定定理CF2800

Hdu5403 Goldbach

题目描述

For a positive integer xx, let d(x)d(x) be the sum of its positive divisors. Call xx a good number if every integer from 11 through d(x)d(x) can be written as a sum of distinct positive divisors of xx.

For example, 66 is good. Its divisors sum to 1+2+3+6=121+2+3+6=12. In particular, 4=1+34=1+3, 5=2+35=2+3, and 7=1+67=1+6.

Teacher Mai wants to determine whether a given even integer pp can be expressed as the sum of two good numbers.

输入格式

Read test cases until the end of the input. Each test case consists of one line containing an even integer pp with 1≤p≤10181\le p\le10^{18}.

There are about 4000040000 test cases. Most are generated randomly.

输出格式

For each test case, print YES if such a decomposition exists, and NO otherwise.

If the answer is YES, print good numbers a,ba,b with a+b=pa+b=p on the next line. Then print two more lines containing the prime factorizations of aa and bb, respectively.

For a factorization x=∏i=1kpieix=\prod_{i=1}^{k}p_i^{e_i}, where the pip_i are distinct primes in increasing order and ei≥1e_i\ge1, print kk followed by the 2k2k space-separated integers p1,e1,…,pk,ekp_1,e_1,\ldots,p_k,e_k. The factorization line for 11 is 0.

18
YES
6 12
2 2 1 3 1
2 2 2 3 1

提示

00 is excluded from the good numbers.