当前位置：网站首页>Cf365-e - Mishka and divisors, number theory +dp

Cf365-e - Mishka and divisors, number theory +dp

2022-07-25 15:34:00 【Brother Tazi is here】

The main idea of the topic :

to n ( n ≤ 1000 ) n(n \leq 1000) n(n≤1000) Number , Multiply with the least number to get k ( ≤ 1 e 12 ) k(\leq 1e12) k(≤1e12) Multiple .

Topic ideas :

Make d p ( i , j ) dp(i,j) dp(i,j) On behalf of i i i Number , Multiplicative gain j j j The minimum number of multiples of (01 knapsack )
j j j Take only k k k The divisor of .

For the first i i i Number , Transfer to :
d p ( i , j ) = m i n ( d p ( i − 1 , j ) , d p ( i − 1 , j g c d ( a i , j ) ) + 1 ) dp(i,j)=min(dp(i-1,j),dp(i-1,\frac{j}{gcd(a_i,j)})+1) dp(i,j)=min(dp(i−1,j),dp(i−1,gcd(ai​,j)j​)+1)

Why must it be from j g c d ( a i , j ) \frac{j}{gcd(a_i,j)} gcd(ai​,j)j​ Transferred to the j j j Well ?

原网站

版权声明
本文为[Brother Tazi is here]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/206/202207251523347765.html

边栏推荐

猜你喜欢

随机推荐