POJ 1426 Find The Multiple (附模运算公式)

本文主要是介绍POJ 1426 Find The Multiple (附模运算公式)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意: 

找到由‘1’ 和 ‘0’ 组成的第一个能被n整除的十进制数

分析:

1. big = 1开始, big * 10 和 big * 10 + 1进行BFS遍历, 直到 big mod n == 0

2. 剪枝处理多余的搜索(暴力搜索会TLE)

3. 实现代码.

看完题我以为是大数处理, '0' '1' 需要放在数组中. 分析思路迷茫 搜了下...(不好的习惯,  这些日子只想着做BFS DFS的题,  没想太多(⊙o⊙)…）

搜完知道了所有数据量最大才19位, __int64 就OK的了. so... BFS暴力, TLE.

继续搜, 看到有人说用 

(A+B )  mod MOD=(A  mod MOD + B mod MOD)  mod MOD

 (A*B )  mod MOD=(A  mod MOD*B mod MOD)  mod MOD

公式，自己试了很久没有出来,  别人用这个的思路也没搞懂.

再搜别的思路, 还是迷迷瞪瞪的, 是懂非懂. 

别人用的是鸽巢原理。(看到此篇文章并且懂为什么的人, 希望求教, 谢谢!!)

#include <iostream>
#include <queue>
using namespace std;
int visited[202];
__int64 BFS(int mod)
{__int64 temp, big;queue<__int64> q;q.push(1);while (!q.empty()){big = q.front();q.pop();if (big % mod == 0)return big;//加 '0' 操作temp = big * 10;if (visited[temp % mod] == 0){visited[temp % mod] = 1;q.push(temp);}//加 '1' 操作temp = big * 10 + 1;if (visited[temp % mod] == 0){visited[temp % mod] = 1;q.push(temp);}}return -1;
}
int main()
{int mod;while (scanf("%d", &mod) && mod){memset(visited, 0, sizeof(visited));printf("%I64d\n", BFS(mod));}return 0;
}

//百度摘抄
四则运算规则:(^指代幂, 非位运算)1.(A + B) mod MOD=(A mod MOD + B mod MOD) mod MOD2.(A - B) mod MOD=(A mod MOD - B mod MOD) mod MOD3.(A * B) mod MOD=(A mod MOD * B mod MOD) mod MOD4.(A ^ B) mod MOD=((A mod MOD) ^ B) mod MOD结合律:1.((A + B) mod MOD + C) mod MOD=(A + (B + C) mod MOD) mod MOD2.((A * B) mod MOD * C) mod MOD=(A * (B * C) mod MOD) mod MOD交换律:1.(A + B) mod MOD=(B + A) mod MOD2.(A * B) mod MOD=(B * A) mod MOD分配率:1.((A + B) mod MOD * C) mod MOD=((A * C) mod MOD + (B * C) mod MOD) mod MOD重要定理:1.若A ≡ B (mod MOD), 则对于任意的C, 都有(A + C) ≡ (B + C)(mod MOD);2.若A ≡ B (mod MOD), 则对于任意的C, 都有(A * C) ≡ (B * C)(mod MOD);3.若A ≡ B (mod MOD), C ≡ D (mod MOD),则(A + C) ≡ (B + D)(mod MOD), (A - C) ≡ (B - D)(mod MOD),(A * C) ≡ (B * D)(mod MOD), (A / C) ≡ (B / D)(mod MOD);4.若A ≡ B (mod MOD), 则对于任意的C, 都有AC ≡ BC(mod MOD);基本性质:1.若MOD|(A - B), 则A ≡ B(mod MOD).2.(A  mod MOD) = (B mod MOD) 意味 A ≡ B(mod MOD)3.对称性: A ≡ B (mod MOD)等价于B ≡ A(mod MOD)4.传递性: 若A ≡ B(mod MOD)且B ≡ C(mod MOD), 则A ≡ C(mod MOD)

这篇关于POJ 1426 Find The Multiple (附模运算公式)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---