← 返回题目列表

Codeforces · 396/E

E. 关于一个众所周知的函数的迭代

中文机器翻译题面 查看原题

当然,你们中的许多人都可以计算 φ(n) — 小于或等于 n 且与​​ n 互质的正整数的数量。但是,如果我们需要计算 φ(φ(...φ(n))),其中函数 φ 被取 k 次,并且 n 在规范分解为质因数中给出,该怎么办?

给定 n 和 k,计算 φ(φ(...φ(n))) 的值。打印典型分解为质因数的结果。

输入

第一行包含整数 m (1 ≤ m ≤ 105) — n 的规范表示中不同素因数的数量。

接下来的 m 行中的每一行都包含一对空格分隔的整数 pi, ai (2 ≤ pi ≤ 106; 1 ≤ ai ≤ 1017) — 数字 n 的另一个素因数及其在规范表示中的幂。所有 ai 的总和不超过 1017。输入中的质因数严格按照递增顺序排列。

最后一行包含整数 k (1 ≤ k ≤ 1018)。

输出

在第一行中,打印整数 w — 数字 φ(φ(...φ(n))) 的不同质因数的数量,其中函数 φ 被取 k 次。

接下来的 w 行必须包含两个以空格分隔的整数 qi, bi (bi ≥ 1) — 另一个素除数及其在结果的规范表示中的幂。数字 qi 必须严格按照递增顺序排列。

示例

输入 #1

1
7 1
1

输出 #1

2
2 1
3 1

输入 #2

1
7 1
2

输出 #2

1
2 1

输入 #3

1
2 100000000000000000
10000000000000000

输出 #3

1
2 90000000000000000

注意

您可以在这里阅读有关正整数的规范表示:http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic。

您可以在这里阅读有关函数 φ(n) 的信息:http://en.wikipedia.org/wiki/Euler's_totient_function。