好吧,一开始的做法不太对,不过关于这一题,有一个非常巧妙的方法证明答案 $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 中了解到的,其中有很多巧妙的证明,推荐去看看 |
|
#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。。。。。。
题目 1303 [HAOI 2012初中]01数字
2017-11-13 21:18:07
|
|
我能怎么办。。。枚举256比枚举30000还慢
|
|
水
|
|
嗯,这题真的可以说难度不大,怪不得是“初一必过”。
|
|
水题水题水题水题
这都一颗星???不应该空心吗? |
|
|
|
这题·················不能懒省事啊!!!!
此题有Bug,@ Letter zZZz 你代码中的Bug已纠正 |
|
这速度有点快的说(我的代码有漏洞的说)
|
|
喵喵……
|