#yukicoder390E ''' 正整数Nが与えられる。Mは自由に選んで良い。 1から初めて、単調増加し、最終的にNになる。 隣接項はA[i]との最小公倍数になる。うーん、むずかしいぞ。 入力例を読もう。 なるほど。単に素因数を配列すればよい、という問題ではないわけだ。 それはそれとして素因数分解は必要だな。 上位の約数に遷移する、と考えればよさそうだ。 元々持っていた素因数は減らせないから、 1. もともと持っていた素因数ぶんは自由に使ってよい。 2. 増やすと決めた素因数は値が固定される。 増やさない範囲で他のものをいじってよい。 大小関係は常に単調増加することが保証されるから大丈夫でしょう。 963761198400=2^6*3^4*5^2*7^1*11^1*13^1*17^1*19^1*23^1 約数は最大6720個。ま、DPでしょうかね。 ''' #素因数分解し、(素因数,次数)の順に格納したリストを返す def Soinsu(CheckNumber): SoinsuList=[] for Soinsu in range(2,CheckNumber): if Soinsu*Soinsu>CheckNumber:break if CheckNumber%Soinsu!=0:continue SoinsuCount=0 while CheckNumber%Soinsu==0:SoinsuCount+=1;CheckNumber//=Soinsu SoinsuList.append((Soinsu,SoinsuCount)) if CheckNumber!=1:SoinsuList.append((CheckNumber,1)) return SoinsuList #xの約数を全列挙する。0以下の値の場合、[]を返す。 def divisor(x): Ldiv,Udiv=[],[] for i in range(1,x+1): if i**2>x:break if x%i==0: Ldiv.append(i) if i**2!=x:Udiv.append(x//i) return Ldiv+Udiv[::-1] from itertools import combinations as cb gcd=lambda x,y: gcd(y,x%y) if x%y else y N=int(input()); MOD=998244353; P=Soinsu(N); E=[P[i][1] for i in range(len(P))] base=[1] for i in range(len(P)-1): base.append(base[-1]*(E[i]+1)) hash=lambda T: sum(T[i]*base[i] for i in range(len(T))) rev =lambda H: tuple([H%base[i]//base[i-1] for i in range(1,len(base))]+[H//base[-1]]) DP=[1]+[0]*hash(E) for num in range(len(DP)): H=rev(num); choice=set() #choice[i]: まだ上昇余地がある因子 for i in range(len(H)): if H[i]