题目名称 1303. [HAOI 2012初中]01数字
输入输出 torch.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarsywgz 于2013-03-08加入
开放分组 全部用户
提交状态
分类标签
HAOI 基本
分享题解
通过:132, 提交:160, 通过率:82.5%
Gravatar合金装备布狼牙 100 0.000 s 0.00 MiB C++
Gravatar乐未殇 100 0.000 s 0.00 MiB C++
GravatarApocana-Wisbtsml 100 0.000 s 0.00 MiB C++
Gravatar1020 100 0.000 s 0.00 MiB C++
Gravatarsudv 100 0.000 s 0.00 MiB C++
Gravataryrtiop 100 0.000 s 0.00 MiB C++
Gravatar䱖虁職 100 0.000 s 0.00 MiB C++
Gravatarlihaoze 100 0.000 s 0.00 MiB C++
Gravatarop_组撒头屯 100 0.000 s 0.00 MiB C++
GravatarHeSn 100 0.000 s 0.00 MiB C++
本题关联比赛
20130802初中
2009noip模拟试卷
关于 01数字 的近10条评论(全部评论)
好吧,一开始的做法不太对,不过关于这一题,有一个非常巧妙的方法证明答案 $m$ 一定存在。
设一个序列 $f(n) = 1, 11, 111, 1111, 11111 ...$,易知序列中任意两个数做差的结果只由 $1, 0$构成,又因为任意一个正整数 $mod n $ 的值一定不会超过 $n$ ,因此,根据鸽笼原理,一定存在两个数 $x, y \in f(n)$,使得这两个数对 $n$ 取模的值相等,对这两个数做差,得到的数就是 $n$ 的倍数,除以 $n$ 之后,就得到一个数 $m$ 满足条件,不过这个方法求出来的不一定是最小值,实测只能过 $4$ 个点。不过由于这一题的数据规模不大,所以暴力也能很好的求解。这一巧妙的证明方法我是在 matrix67 大佬的 Blog 中了解到的,其中有很多巧妙的证明,推荐去看看
Gravatarlihaoze
2022-03-20 00:45 10楼
#include <iostream>
#include<cstdio>
using namespace std;
int main() {
freopen("torch.in","r",stdin);
freopen("torch.out","w",stdout);
int n,t=1,tt,a;
cin>>n;
for(;;)
{tt=t*n;
for(;;)
{a=tt%10;
if(a>1) {tt=t*n;break;}
tt=tt/10;
if(tt==0) break;}
if(tt==0)
{cout<<t;break;}
t++;}
return 0;
}
渣程序仅供参考。。。。。。
tmd读错题了,以为m也必须是由0,1组成的,调试了20+min。。。。。。
GravatarShallowDream雨梨
2017-11-13 21:18 9楼
我能怎么办。。。枚举256比枚举30000还慢
GravatarkZime
2017-07-11 11:04 8楼
Gravatar牧殇
2016-10-09 19:49 7楼
嗯,这题真的可以说难度不大,怪不得是“初一必过”。
GravatarGaoErFu
2015-08-15 21:33 6楼
水题水题水题水题
这都一颗星???不应该空心吗?
GravatarNVIDIA
2015-07-12 11:45 5楼
Gravatar甘罗
2014-07-13 09:01 4楼
这题·················不能懒省事啊!!!!
此题有Bug,@ Letter zZZz 你代码中的Bug已纠正
Gravatar752199526
2014-04-19 22:24 3楼
这速度有点快的说(我的代码有漏洞的说)
GravatarLetter zZZz
2014-04-19 22:18 2楼
喵喵……
Gravatarcstdio
2013-03-17 17:30 1楼

1303. [HAOI 2012初中]01数字

★★   输入文件:torch.in   输出文件:torch.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

任意给定一个正整数N(N≤10000),求一个最小的正整数M,使得N*M的十进制表示形式里只含1和0.

【输入格式】

仅一个正整数N。

【输出格式】

如果有解,输出最小的M,否则输出NO(大写)。

【样例输入】

12

【样例输出】

925

【提示】

全部数据保证答案不超过30000. N*M≤10^8。