如何找到只有 0 和 1 除以给定数字的最小数字?

编程入门 行业动态 更新时间:2024-10-24 20:22:39
本文介绍了如何找到只有 0 和 1 除以给定数字的最小数字?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧! 问题描述

每个正整数除以表示(以 10 为底)仅包含零和一的数字.

Every positive integer divide some number whose representation (base 10) contains only zeroes and ones.

可以证明:

考虑数字 1、11、111、1111 等,直到 111...1,其中最后一个数字有 n+1 位数字.称这些数字为 m1、m2、...、mn+1.每个都有一个除以 n 时的余数,且其中两个余数必须相同.因为它们有 n+1 个,但余数只能取 n 个值.这是著名而有用的鸽巢原理"的应用;

Consider the numbers 1, 11, 111, 1111, etc. up to 111... 1, where the last number has n+1 digits. Call these numbers m1, m2, ... , mn+1. Each has a remainder when divided by n, and two of these remainders must be the same. Because there are n+1 of them but only n values a remainder can take. This is an application of the famous and useful "pigeonhole principle";

假设余数相同的两个数是mi和mj, 与我 <j.现在从较大的减去较小的.结果数 mi−mj 由 j - i 个 1 和 i 个零组成,必须是 n 的倍数.

Suppose the two numbers with the same remainder are mi and mj , with i < j. Now subtract the smaller from the larger. The resulting number, mi−mj, consisting of j - i ones followed by i zeroes, must be a multiple of n.

但是如何找到最小的答案呢?并且有效?

But how to find the smallest answer? and effciently?

推荐答案

好问题.我使用 BFS 通过中间相遇和其他一些修剪来解决这个问题.现在我的代码可以在合理的时间内解决 n<109.

Nice question. I use BFS to solve this question with meet-in-the-middle and some other prunings. Now my code can solve n<109 in a reasonable time.

#include <cstdio> #include <cstring> class BIT { private: int x[40000000]; public: void clear() {memset(x, 0, sizeof(x));} void setz(int p, int z) {x[p>>5]=z?(x[p>>5]|(1<<(p&31))):(x[p>>5]&~(1<<(p&31)));} int bit(int p) {return x[p>>5]>>(p&31)&1;} } bp, bq; class UNIT { private: int x[3]; public: int len, sum; void setz(int z) {x[len>>5]=z?(x[len>>5]|(1<<(len&31))):(x[len>>5]&~(1<<(len&31)));} int bit(int p) {return x[p>>5]>>(p&31)&1;} } u; class MYQUEUE { private: UNIT x[5000000]; int h, t; public: void clear() {h = t = 0;} bool empty() {return h == t;} UNIT front() {return x[h];} void pop() {h = (h + 1) % 5000000;} void push(UNIT tp) {x[t] = tp; t = (t + 1) % 5000000;} } p, q; int n, md[100]; void bfs() { for (int i = 0, tp = 1; i < 200; i++) tp = 10LL * (md[i] = tp) % n; u.len = -1; u.sum = 0; q.clear(); q.push(u); bq.clear(); while (1) { u = q.front(); if (u.len >= 40) break; q.pop(); u.len++; u.setz(0); q.push(u); u.setz(1); u.sum = (u.sum + md[u.len]) % n; if (!bq.bit(u.sum)) {bq.setz(u.sum, 1); q.push(u);} if (!u.sum) { for (int k = u.len; k >= 0; k--) printf("%d", u.bit(k)); puts(""); return; } } u.len = 40; u.sum = 0; p.clear(); p.push(u); bp.clear(); while (1) { u = p.front(); p.pop(); u.len++; u.setz(0); p.push(u); u.setz(1); u.sum = (u.sum + md[u.len]) % n; if (!bp.bit(u.sum)) {bp.setz(u.sum, 1); p.push(u);} int bf = (n - u.sum) % n; if (bq.bit(bf)) { for (int k = u.len; k > 40; k--) printf("%d", u.bit(k)); while (!q.empty()) { u = q.front(); if (u.sum == bf) break; q.pop(); } for (int k = 40; k >= 0; k--) printf("%d", u.bit(k)); puts(""); return; } } } int main(void) { // 0 < n < 10^9 while (~scanf("%d", &n)) bfs(); return 0; }

更多推荐

如何找到只有 0 和 1 除以给定数字的最小数字?

本文发布于:2023-11-30 21:30:00,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1651528.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:数字   最小

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!