同余模定理解决大数问题（poj1426）

解题方法： BFS+同余模定理

首先我们简单回顾一下 朴素搜索 法：

n=6

?

1%6=1? (k=1)

{?

?(1*10+0)%6=4? (k=10)

{

????(10*10+0)%6=4?? (k=100)

??? {

????????(100*10+0)%6=4? (k=1000)

??????? (100*10+1)%6=5? (k=1001)

??? }

??? (10*10+1)%6=5? (k=101)

??? {

????????(101*10+0)%6=2? (k=1010)

??????? (101*10+1)%6=3? (k=1011)

??? }

}

?? (1*10+1)%6=5? (k=11)

{

??? (11*10+0)%6=2?? (k=110)

??? {

????????(110*10+0)%6=2? (k=1100)

??????? (110*10+1)%6=3? (k=1101)

??? }

????(11*10+1)%6=3?? (k=111)

??? {

??????? (111*10+0)%6=0? (k=1110)?? 有解

??????? (111*10+1)%6=1? (k=1111)? 由于前面有解，这个余数不存储

??? }

}

}

从上面可以看出余数的存数顺序（逐层存储）：

用数组mod[]存储余数，其中mod[0]不使用，由mod[1]开始

那么mod中的余数依次为：?1 4 5 4 5 2 3 4 5 2 3 2 3 0??共14个

即说明我们得到 余数0 之前，做了14步*10的操作，那么当n值足够大的时候，是很容易出现k为大数的情况（事实上我做过统计，200以内的n，有18个n对应的k值为大数

?

那么我们再用int去存储k就显得不怎么明智了。

为了处理所有情况，我们自然会想到 是不是应该要用int[]去存储k的每一位？

而又由于k是一个01序列，那能不能把?*10得到k每一位的问题?转化为模2的操作得到k的每一位(0或1)?呢？

答案是可以的

利用?同余模定理?对得到余数的方式进行一个优化

（a*b）%n = （a%n *b%n）%n

（a+b）%n = （a%n +b%n）%n

随便抽取上面一条式子为例

前一步 (11*10+1)%6=2?? 即k=110 ， k%6=2

当前步 (110*10+1)%6=2

由同余模定理??(110*10+1)%6 = (（110*10）%6+1%6 )%6 = (（110%6 * 10%6）%6 +1 )%6

不难发现下划线部分110%6等于 (11*10+0)%6 = 2

所以当前步(110*10+1)%6可以转变为? (2*10+1)%6=2

?

很显然地，这种处理把k=110 等价于 k=2

即用?前一步操作得到的余数?代替?当前步的k值

而n在200的范围内， 余数值不可能超过3位数， 这就解决了?大数的问题

?

通过这种处理手法，我们只需在BFS时顺手存储一个 余数数组mod[] ，就能通过mod[i-1]得到mod[i]? ，直到mod[i]==0 时结束，大大减少了运算时间

?

前面已经提到，n=6时，求余操作进行了14次，对应地，BFS时*10的操作也进行了14次。

令i=14，通过观察发现，i%2恰好就是 6 的倍数的最低位数字

i/2? 再令 i%2 ，恰好就是 6 的倍数的 次低位数字。。。

循环这个操作，直到i=0，就能得到 6的 01倍数(一个01队列)，倒序输出就是所求

这样就完成了 *10操作到 %2操作的过渡

源码：

#include<iostream>
using namespace std;

int mod[524286];  
    
int main(int i)
{
	int n;
	while(cin>>n)
	{
		if(!n)
			break;

		mod[1]=1%n;  //初始化，n倍数的最高位必是1

		for(i=2;mod[i-1]!=0;i++)  //利用同余模定理，从前一步的余数mod[i/2]得到下一步的余数mod[i]
			mod[i]=(mod[i/2]*10+i%2)%n;
		             //mod[i/2]*10+i%2模拟了BFS的双入口搜索
		             //当i为偶数时，+0，即取当前位数字为0  。为奇数时，则+1,即取当前位数字为1

		i--;
		int pm=0;
		while(i)
		{
			mod[pm++]=i%2;   //把*10操作转化为%2操作，逆向求倍数的每一位数字
			i/=2;
		}
		while(pm)
			cout<<mod[--pm];  //倒序输出
		cout<<endl;
	}
	return 0;
}

解法二：

用队列模拟广搜，这道题其实在long long的范围内可以解决，所以下面这个方法更容易想到

#include <iostream>
#include <queue>
using namespace std;
int n;
long long bfs()
{
     queue<long long> p;
     while(!p.empty())
     p.pop();
     p.push(1);
     while(1)
     {
             long long sum=p.front();
             if(sum%n==0)
             return sum;
             p.pop();
             p.push(10*sum);
             p.push(10*sum+1);
     }
}
int main()
{
    while(cin>>n,n)
    {
                   cout<<bfs()<<endl;
    }
    return 1;
}