当然,你们中的许多人都可以计算 φ(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。