数论 - 同余 + BFS (Find The Multiple)
2024-09-03 13:14:01
Find The Multiple
Time Limit: 1000MS | Memory Limit: 10000K | |||
Total Submissions: 16995 | Accepted: 6921 | Special Judge |
Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2
6
19
0
Sample Output
10
100100100100100100
111111111111111111
【题目大意】
给出一个整数n,(1 <= n <= 200)。求出任意一个它的倍数m,要求m必须只由十进制的'0'或'1'组成。
【题目分析】
数论 +bfs
用到了同余定理,用bfs搜索当前位,每位都只可能是0或1,所以这是双入口的bfs,同时还涉及到了大数的知识。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int mod[];
int main(int i)
{
int n;
while(cin>>n)
{
if(!n)
break; mod[]=%n;
for(i=;mod[i-]!=;i++)
mod[i]=(mod[i/]*+i%)%n;
i--;
int pm=;
while(i)
{
mod[pm++]=i%;
i/=;
}
while(pm)
cout<<mod[--pm]; //倒序输出
cout<<endl;
}
return ;
}
最新文章
- wpf 逻辑树与可视化树
- 2.C语言中的关键字
- Linux服务器文件删除空间未释放的问题
- [No00004F]史上最全Vim快捷键键位图(入门到进阶)
- java四大名著
- 对OCR文字识别软件的扫描选项怎么设置
- 监听器Listener
- laravel步骤 (我是新手)
- eclipse 错误: 找不到或无法加载主类
- c#以文件流的形式输出xml(可以解决内存溢出)-XmlTextWriter
- 神经网络 误差逆传播算法推导 BP算法
- nfc近场通信
- 中科曙光I620-G15服务器登录密码破解
- python中文分词库——pyltp
- sqlserver备份还原数据库时报占用错误
- Android---------------Activity的学习
- yum install mysql56
- 免费json API
- VBA替换函数
- 利用vbs设置Java环境变量