173题:本原串

中等
题目描述:

由0和1组成的串中,不能被分解为多个相同子串的字符串称为本原串。例如,100100不是本原串,因为它能被分解为两个100;而1101是本原串,因为它不能被分解为多个相同的子串。请你计算长度为n(0<n<=100000000)的0-1串中,有多少个本原串?由于最终的结果可能会很大,因此请输出答案%2017(答案数取模2017)

例如:
  n = 1, 则输出:2
  n = 2, 则输出:2

说明:长度为1的本原串有两个,分别为"0"、"1"; 长度为2的本原串也有两个,分别为"01"、"10"。

示例:

输入:n = 1

输出:2

提交次数:
144
通过次数:
100
通过率:
69.44%
相似题目
请选择语言:
请点击"执行代码"或"提交"按钮