ZOJ Monthly, September 2012

Problem A. Kitty’s Game
有一隻喵身上有個記分牌,每個點上有一個全值 pi,她每沿著邊走一步,記分牌上的數字就會變為這兩個數字的 lcm。
問從起點S走到終點T,最後記分牌上數字為 k 的方案有多少種。(要求每一步記分牌上的數字都必須發生變化。
Tags: DP
略。( .. 注意到 lcm 單調遞增,用這個值劃分階段即可。。
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=711276

ゆっくり読んでください …