← 返回题目列表

AtCoder · icpc2013summer_day3_d

D. 快速除法

中文机器翻译题面 查看原题

Ikta 喜欢快速程序。最近,我一直在努力使除法程序更快。然而,由于很难提高速度,因此我认为仅对“基于常识的典型”输入提高速度是适当的。 Ikta试图解决的问题如下。

给定非负整数n以十进制表示p(n) - 1带数字的正整数 除以11...1请计算p(n)后求余数。然而p(n)是22{...2}(2 是 让它代表大于n的最小质数。p(0) = 2。

你的任务是比 Ikta 更快地完成程序。

输入

输入按以下格式给出。

n

问题输入的非负整数 给出了n。

约束

输入中的每个变量都满足以下约束。

  • 0 \leq n < 1000

输出

将问题的解决方案打印在一行上。

示例输入 1

0

样本输入 1 的输出

1
  • n=0时, 一只狼已经坐在p(n) = 2 ,所以 1 mod 2 = 1 就是解。

示例输入 2

1

样本输入 2 的输出

2
  • n=1时, 一只狼已经坐在p(n) = 3 因此,11 mod 3 = 2 就是解。

示例输入 3

2

样本输入 3 的输出

1