這是前天成都網賽的題，比賽時候確實一點思路也沒有。比完之后看了人家的解題報告，還是不會怎么搜出答案，太弱了。
題意是給出N,K，求M，使得M是N的正倍數，而且M用K進制表示后所需要的不同數字(0,1,2,3,...,k-1)最少，如果有多組
這樣的情況，求出最小的M。
很數學的題意。用到了一個結論，就是任意數字的正倍數均可以用不超過2個不同數字的數得到。
證明如下：
任意數M % N 總共有N種結果，假如有N+1個不同的M，那么肯定有2個M對N取模后的結果是相同，這個是所謂鴿巢原理。
那么，我取a,aa,aaa,...,aaaaaaaaaa....，總共N+1個，同樣滿足上面的結論。那么我取那2個對N取模相同的數字相減得到
數字aaaaa...000....，這個數字肯定是N的倍數。
綜合上面的證明，只能得到2個數字肯定能表示N的倍數。但是不能說形式就是aaaaa...000....。
到了這里我還是一點思路都沒有，一點都不知道怎么搜索。。。
想了1個多小時，無頭緒，問過了這題的同學，還是無頭緒。看解題報告，他們的代碼寫得太牛了，完全看不懂，無頭緒。
也許也是我對bfs理解太淺，才看不懂他們的搜索代碼。而且，我連可以搜索的地方都沒有找到，都不知道搜什么了。
想了好久，昨天吃飯的時候，終于發現可以對余數進行搜索。
對于任意的N，其余數就是范圍是[0, N -1]。這個其實就可以代表狀態了，或者代表bfs中的點了。從當前余數轉移到其它
余數的是MOD * K + A 或者 MOD * K + B，如果要轉移到得余數以前沒被搜過，那就可以轉移過去。這個剛好就是一個
優化了。也可以看成是子問題了。但是，dfs完全不行。剛開始用dfs，絕對的超時。
用dfs也是我對思路理解不深，僥幸認為能過。。。后面發現，這題完全和bfs吻合。[0, N -1]剛好代表N個點，我要通過
從外面的一個點，最短的遍歷到點0，可以bfs或者最短路算法。這題我覺得還有個難點就是保存答案，因為答案最長的長度
可能是N(N<=10000)，所以把答案直接放到節點里面肯定不行的。但是，我還仔細看過算法導論。因此想到了可以利用bfs
搜索出來的那顆樹或者最短路算法跑出來的那顆樹，從目標節點逆序尋找答案，找到出發節點之后，再把答案reverse一下就行了。
這題還得注意0不能是N的倍數，所以注意bfs(0,i)這種情況的處理。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX_N = 10010;
int nOut[MAX_N];
int nOLen;
int nAns[MAX_N];
int nALen;
bool bMod[MAX_N];
int nFather[MAX_N];
int nChoose[MAX_N];
int nN;
int nK;
bool bFind;
int Cmp(
int* A,
int nLA,
int* B,
int nLB)
{
if (nLA != nLB)
{
return nLA - nLB;
}
for (
int i = 0; i < nLA; ++i)
{
if (A[i] != B[i])
{
return A[i] - B[i];
}
}
return 0;
}
void Bfs(
int nA,
int nB)
{
memset(bMod,
false,
sizeof(bMod));
queue<
int> que;
que.push(0);
int nTemp;
bool bFirst =
true;
bFind =
false;
if (nA > nB)swap(nA, nB);
//printf("nA:%d, nB:%d\n", nA, nB);
while (!que.empty())
{
//printf("nMod:%d\n", que.front());
int nMod = que.front();
que.pop();
if (nMod == 0)
{
if (bFirst)bFirst =
false;
else {
bFind =
true;
break;
}
}
nTemp = (nMod * nK + nA) % nN;
if (!(nMod == 0 && nA == 0) && !bMod[nTemp])
{
nFather[nTemp] = nMod;
nChoose[nTemp] = nA;
que.push(nTemp);
bMod[nTemp] =
true;
//printf("nTemp:%d\n", nTemp);
}
if (nA == nB)
continue;
nTemp = (nMod * nK + nB) % nN;
if (!bMod[nTemp])
{
nFather[nTemp] = nMod;
nChoose[nTemp] = nB;
que.push(nTemp);
bMod[nTemp] =
true;
//printf("nTemp:%d\n", nTemp);
}
}
if (bFind)
{
int nF = 0;
nALen = 0;
do {
nAns[nALen++] = nChoose[nF];
nF = nFather[nF];
}
while (nF);
reverse(nAns, nAns + nALen);
}
}
int main()
{
while (scanf("%d%d", &nN, &nK) == 2)
{
bool bOk =
false;
nOLen = 0;
for (
int i = 1; i < nK; ++i)
{
Bfs(i, i);
if (bFind)
{
if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
{
nOLen = nALen;
memcpy(nOut, nAns,
sizeof(
int) * nALen);
}
bOk =
true;
}
}
if (!bOk)
for (
int i = 0; i < nK; ++i)
{
for (
int j = i + 1; j < nK; ++j)
{
Bfs(i, j);
if (bFind)
{
if (nOLen == 0 || Cmp(nOut, nOLen, nAns, nALen) > 0)
{
nOLen = nALen;
memcpy(nOut, nAns,
sizeof(
int) * nALen);
}
}
}
}
for (
int k = 0; k < nOLen; ++k)
{
printf("%d", nOut[k]);
}
printf("\n");
}
return 0;
}