#P2557. [AHOI2002] 芝麻开门

[AHOI2002] 芝麻开门

题目描述

周末小可可参加智力大冲浪活动,经过努力终于来到最后一关“芝麻开门”。门上的电子显示屏写着这么一段话:如果你能把 nkn^k 的所有正整数因子的和正确地写在门上,并念一声“芝麻开门”,门就能够自由打开。

例如:n=2n=2k=3k=3,则 nk=8n^k=8,它的正因子有 1,2,4,81,2,4,8,如果小可可把它们的和 1515 写在门上,然后念一声“芝麻开门”,门就能够自动打开。

已知门上的 n,kn,k 都是每过一段时间就会变化一次,请你编写程序协助小可可在规定的时间内求出答案,从而获得智力大冲浪的最终大奖。

输入格式

一行两个正整数 n,kn,k

输出格式

一行一个整数表示答案。

1 1
1
2 2
7

提示

1n2161\le n \le 2^{16}1k<201\le k \lt 20

解的位数不超过 100100 位。