問題：
任意給定一個正整數N，求一個最小的正整數M(M>1)，使得N*M的十進制表示形式裡只含有1和0。
解法：
由於沒有直接的數學方法能幫我們直接得到M的值，所以我們只能進行搜索。由於相對M，乘積N*M具有明顯的特征，需要搜索的空間要小很多，所以我們對乘積N*M進行搜索。如果N*M的結果有K位，則要循環2^K次，我們發現K的結果能輕易超過40，所以這個運行時間還是相當長。
同余運算具有等價關系，mod N = i（0<=i<N）構成了N個等價類，將正整數集進行劃分。對於每個等價類，我們只需要判斷其中最小的元素加上10^K是否能被N整除，這樣搜索空間就從2^K次減少到(K-1)*N步，而N的值一般要遠遠小於M的值。但要O(N)的空間復雜度。
我們可以證明對於任意的N，一定存在M，使得N*M的乘積的十進制表示只有0和1。證明過程見由於無論M還是N*M的位數都相當大，所以我們用大整數表示M和N*M。由於要N個大整數，所以N不能為大整數，即其值最好取一百萬以內。
[cpp]
#include <iostream>
#include <cstring>
using namespace std;
// 大整數類型
#define MAXLEN 100
struct HP {int len, s[MAXLEN];};
void PrintHP(const HP &x)
{
for (int i=x.len; i>=1; i--)
cout << x.s[i];
}
// 字符串轉大整數
void Str2HP(const char *s, HP &x)
{
x.len = strlen(s);
for (int i=1; i<=x.len; i++)
x.s[i] = s[x.len-i] - '0';
if (x.len == 0)
{
x.len = 1;
x.s[1] = 0;
}
}
// 大整數的加法
void Plus(const HP a, const HP b, HP &c)
{
int i; c.s[1] = 0;
// 大整數a,b的加法操作和結果c的進位操作
for (i=1; i<=a.len || i<=b.len || c.s[i]; i++)
{
if (i <= a.len) c.s[i] += a.s[i];
if (i <= b.len) c.s[i] += b.s[i];
c.s[i+1] = c.s[i]/10; c.s[i] %= 10;
}
// 退出循環到原因是c.s[i]==0，所以取前一位
c.len = i-1;
if (c.len == 0) c.len = 1;
}
// 大整數的減法
void Subtract(const HP a, const HP b, HP &c)
{
int i, j;
for (i=1,j=0; i<=a.len; i++)
{
// j表示是否要對高位進行借位
c.s[i] = a.s[i] - j;
if (i <= b.len) c.s[i] -= b.s[i];
if (c.s[i] < 0)
{
// 向高位借位，補10
j = 1;
c.s[i] += 10;
}
else j = 0;
}
c.len = a.len;
while (c.len > 1 && !c.s[c.len]) c.len--;
}
// 大整數的比較
int HPCompare(const HP &x, const HP &y)
{
if (x.len > y.len) return 1;
if (x.len < y.len) return -1;
int i = x.len;
while (i>1 && (x.s[i]==y.s[i])) i--;
return x.s[i] - y.s[i];
}
// 大整數的乘法
void Multi(const HP a, const HP b, HP &c)
{
int i, j;
// 對乘法結果賦初值，以方便之後的+=運算
c.len = a.len + b.len;
for (i=1; i<=c.len; i++) c.s[i] = 0;
for (i=1; i<=a.len; i++)
for (j=1; j<=b.len; j++)
c.s[i+j-1] += a.s[i]*b.s[j];
// 運算結果進位
for (i=1; i<c.len; i++) {c.s[i+1] += c.s[i]/10; c.s[i] %= 10;}
// 最高位繼續進位
while (c.s[i]) {c.s[i+1] = c.s[i]/10; c.s[i] %= 10; i++;}
// 確保最高位不為0
while (i>1 && !c.s[i]) i--;
c.len = i;
}
// 大整數的除法
void Divide(const HP a, const HP b, HP &c, HP &d)
{
int i, j;
// 用余數d存被除數a的前i位數據，用來多次減去除數b，以得到商c
d.len = 1; d.s[1] = 0;
for (i=a.len; i>0; i--)
{
if (!(d.len == 1 && d.s[1] == 0))
{
// i沒移一位，余數d也移位
for (j=d.len; j>0; j--)
d.s[j+1] = d.s[j];
d.len++;
}
d.s[1] = a.s[i];
c.s[i] = 0;
// 余數d大於除數b時，才可以進行減操作
while ((j=HPCompare(d,b)) >= 0)
{
Subtract(d, b, d);
c.s[i]++;
if (j == 0) break;
}
}
c.len = a.len;
while (c.len > 1 && c.s[c.len] == 0)
c.len--;
}
// 十進位右移
void RightShift(HP &x, int k)
{
for (int i=1; i<=x.len-k; i++)
x.s[i] = x.s[i+k];
x.len -= k;
if(x.len <= 0)
{
x.len = 1;
x.s[1] = 0;
}
}
// 十進位左移
void LeftShift(HP &x, int k)
{
int i;
for (i=x.len; i>=1; i--)
x.s[i+k] = x.s[i];
for (i=k; i>=1; i--)
x.s[i] = 0;
x.len += k;
}
#define MAXREM 1000000
HP rem[MAXREM];
int main()
{
int i, j, k, N;
char str[MAXREM];
HP one, tmp;
one.len = 1; one.s[1]=1;
while (cin >> str)
{
N = atoi(str);
if (N > MAXREM)
{
printf("ERROR: N(%d) IS TOO LARGE",N);
continue;
}
// 清空余數信息數組
for (i=0; i<N; i++)
rem[i].len = 0;
// 初始化唯一的個位數1
rem[1] = one;
// i表示當前搜索到N*M的第i位，j表示(10^i)%N
for (i=1,j=10%N; rem[0].len==0; i++,j=(j*10)%N)
{
// tmp表示大整數10^N
tmp = one;
LeftShift(tmp, i);
// 如果數組沒有和tmp同余的數，則添入
if (rem[j].len == 0)
rem[j] = tmp;
for (k=1; k<N; k++)
{
// 遍歷余數信息數組，若新產生出余數不同的數，則添入
int u = (j+k)%N;
// 為了防止剛加入的10^N被計算，加入條件rem[k].len <= i
if (rem[k].len && rem[k].len <= i
&& rem[u].len == 0)
Plus(tmp, rem[k], rem[u]);
if (u == 0)
break;
}
} www.2cto.com
Str2HP(str, tmp);
cout << "N*M: ";
PrintHP(rem[0]);
HP d;
Divide(rem[0], tmp, tmp, d);
cout << endl << "M: ";
PrintHP(tmp);
cout << endl;
}
}
作者：linyunzju
