題目連結:
題目大意:
第一列給定三正整數 T 、 A 、 M (A ≦ 10 ^ 9 、 M ≦ 10 ^ 4),代表接下來有 T 列輸入。每列輸入給定三個整數 a 、 m 、 h (a ≦ A , m ≦ M),請將 a ^ m 轉為 b ^ h × c,並輸出 b 、 c (皆小於 2 ^ 63)
b 、 c 若有多種可能解,請輸出 b 最大的解。
要把 a ^ m 分解為 b ^ h × c ,需要先將 a 作質因數分解。然後將所有 a 的質因數的次方乘上 m ,即是 a ^ m 之質因數分解。
再去看 a ^ m 質因數的次方超過 h ,將其超過的部分截取出來,即是 b 。剩下的質因數次方相乘之後即是 c 之值。
而因為我們要質因數分解 a ,所以我們需要先建一個質數表(因為 a 最大到 10 ^ 9,因此只要找 32000 以內的質數)。之後,再用類似判斷 a 是否為質數的方式去將 a 分解。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。