Skip to content

11537: 【原1537】Ficos的坚持

题目

题目描述

author: CodeVS,greatwall1995 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1537

Description

筛选出了所有有效的字符串,Ficos又陷入了思考:每一个数字背后的含义是什么?在焦头烂额之际,Ficos看到Livia的博客上更新了两篇文章,分别是对L数和 \(Z_q\)集合的研究。

\(L\)数是一个十进制数,其定义如下:

  1. “1”是一个\(L\)数。
  2. 一个以“1”结尾的\(L\)数在末尾加上“0”或“1”都是\(L\)数。
  3. 一个以“0”结尾的\(L\)数在末尾加上“0”是\(L\)数。

\(Z_q\)集合是所有\(q\)的倍数构成的集合,即如果一个数\(k\)能被\(q\)整除,当且仅当它是\(Z_q\)集合的一个元素。

思索片刻后,Ficos想到每一个有效数码串对应了一个\(q\),它的含义即是\(Z_q\)集合中最小的\(L\)数。这些有效字符串最终会转化为一个01串,根据这个01串或许可以直接翻译出约会的时间地点。

现在Ficos希望你能帮助它把每一个\(q\)转化成相应的在\(Z_q\)集合中最小的\(L\)数。

Input Format

一个数\(q\)。

Output Format

输出\(Z_q\)集合中最小的\(L\)数,考虑到这个数字可能很大,所以请输出答案除以\(10^7+9\)所得到的余数。

如果不存在这样的数,请输出“Impossible”!

Sample Input

6

Sample Output

1110

Limits

对于30%的数据,答案不超过\(10^6\),或不存在这样的数;

对于60%的数据,答案不超过\(10^{20}\),或不存在这样的数;

对于100%的数据,\(1 \leq q \leq 10^7\);

Hint

其实这题的数据规模可以出到\(10^{18}\),有兴趣的同学可以想一想。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!