web analytics

POJ1465Multiple BFS+同余剪枝

题目链接:http://poj.org/problem?id=1465

题目大意:

一个基数N。然后有m个数字。

问你一个由M个数字里组成的最小的N倍数。

分析:

这道题按常理都是枚举N的倍数来拆分。

这样就会很大。

所以我们应该逆过来想。

BFS用m个数字组合,组合时组合一个最小的数出来。

至于剪枝。

因为

A=a*N +e 即A%N =e

B= b*N+e即B%N=e

当A  B mod N的余数相同时,如果先出现A 。

在A  后加上一个数 i 时 ,  新的数   C = 10 *a*N + 10 *e+i;

同样  B后加上数 i 时 , D = 10*b*N +10*e+i;    由于C D 前边 10*a*N 和 10*b*N 都是N的倍数 ,则C D mod N 的余数都是有 10*e+i 决定的。

于是 C D  mod N 同余。

因此 A B 同余 都添加上 i 之后 新的两个数C D也是同余的。在无论添加多少个数,新生成的两个数也是同余的。

 

 

Post a Comment

You must be logged in to post a comment.