HDU 1104 Remainder(BFS 同余定理)
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1104
在做这道题目一定要对同余定理有足够的了解，所以对这道题目对同余定理进行总结
首先要明白计算机里的取余计算和数学里的不一样的，计算机里的负数取余可以是负数的。例如-1%11=-1 而数学里的取余是-1%11=10
同余定理： 若a对d取余，和b对d取余的结果是相等的，那么称a,b对d是同余的。记作a≡b(mod d);这是数学里的定义。
下面看同余定理的几个性质： 1，a≡a(mod d) 数字和它本身是同余的 2，如果a≡b(mod d),b≡c(mod d);那么a≡c(mod d); 同余具有传递性、 3，如果a≡b(mod d),c≡e(mod d);那么a+c≡b+e(mod d); 4，如果a≡b(mod d),c≡e(mod d);那么a-c≡b-e(mod d); 5，如果a≡b(mod d),c≡e(mod d);那么a*c≡b*e(mod d); 6，如果ac≡bc(mod m) c!=0;那么 a≡b(mod m/gcd(c,m)) ;gcd(c,m)表示c,m的最大公约数。 7，如果a≡b(mod mi)(i=1,2,…..n) 则a≡b(mod [m1,m2…..mn])；[m1,m2…..mn]表示m1,m2….mn的最小公倍数 8，如果a≡b(mod m)；那么a^n≡b^n(mod m); 以上的性质感觉做题目都没怎么用到，下面的倒是要经常用到 9，(a+b)≡((a%d)+(b%d))(mod d); 10，(a-b)≡((a%d)-(b%d))(mod d); 11，(a*b)≡((a%d)*(b%d))(mod d); 12，请特别注意%运算符不一定满足上面的性质
根据同余定理的性质给一道例题吧。 例题：求解2001 的2003 次方对13的取余数。
首先你可以算一下2001 对13取余的余数，发现是12 。那么根据性质8 2001^2003≡12^2003(mod 13).但是12^2003还是很大。一般可以是找12的几次方和1是对13同余的。可以找到12^2≡1(mod 13). 所以：(12^2)^1001≡1^1001(mod 13); 所以：(12^2)^1001*12≡1^1001*12(mod 13); 所以 12^2003≡12(mod 13).
接下来就是关于这道题目的，9,10,11,12 这四个性质。%不满足是因为%运算不像+，-，* 。例如a*b和b*a 的值是不变的，而a%b和b%a是改变的.我也说不出个所以然来，反正就是%运算会改变原本的状态。
解决办法就是倍增一下，把d变成d*b 那么(a%b)≡(((a%(b*d))%(b%(b*d)))(mod b*d).
#include <iostream>
#include <math.h>
#include <string.h>
#include <string>
#include <queue>
using namespace std;
int vis[1000010];
int n,k,m;
typedef struct Node
{
int num;
int step;
string way;
}Node;
int mod(int a,int b)
{
return (a%b+b)%b;
}
void BFS()
{
Node * term=new Node;
Node *n1=new Node;
n1->num=n;
n1->step=0;
n1->way="";
memset(vis,0,sizeof(vis));
queue<Node*> Queue;
Queue.push(n1);
while(!Queue.empty ())
{
term=Queue.front();
Queue.pop();
if(mod(term->num,k)==mod(n+1,k))
{
printf("%d\n",term->step);
cout<<term->way<<endl;
return;
}
if(vis[mod(term->num+m,k*m)]==0)
{
Node *p=new Node;
p->num=mod(term->num+m,k*m);
p->step=term->step+1;
p->way=term->way+"+";
Queue.push(p);
vis[mod(term->num+m,k*m)]=1;
}
if(vis[mod(term->num-m,k*m)]==0)
{
Node *p=new Node;
p->num=mod(term->num-m,k*m);
p->step=term->step+1;
p->way=term->way+"-";
Queue.push(p);
vis[mod(term->num-m,k*m)]=1;
}
if(vis[mod(term->num*m,k*m)]==0)
{
Node *p=new Node;
p->num=mod(term->num*m,k*m);
p->step=term->step+1;
p->way=term->way+"*";
Queue.push(p);
vis[mod(term->num*m,k*m)]=1;
}
if(vis[mod(mod(term->num,m),k*m)]==0)
{
Node *p=new Node;
p->num=mod(mod(term->num,m),k*m);
p->step=term->step+1;
p->way=term->way+"%";
Queue.push(p);
vis[mod(mod(term->num,m),k*m)]=1;
}
}
puts("0");
return ;
}
int main()
{
while(scanf("%d%d%d",&n,&k,&m)!=EOF)
{
if(n==0&&k==0&&m==0)
break;
BFS();
}
return 0;
}