| 题目名称 | 1668. [SPOJ 1481] 寻找素数项 |
|---|---|
| 输入输出 | primechecker.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-06-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：19， 提交：56， 通过率：33.93% | ||||
 张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.803 s | 0.29 MiB | C++ |
|
mikumikumi |
100 | 0.808 s | 0.29 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.812 s | 0.29 MiB | C++ |
|
张灵犀不和我一般见识真可怕呢（笑 |
100 | 0.828 s | 0.29 MiB | C++ |
 Ezoi_XY |
100 | 0.861 s | 0.29 MiB | C++ |
|
Ezoi_XY |
100 | 0.863 s | 0.29 MiB | C++ |
 cstdio |
100 | 0.871 s | 0.32 MiB | C++ |
 xinyue |
100 | 0.878 s | 0.28 MiB | C++ |
 天一阁 |
100 | 0.879 s | 0.29 MiB | C++ |
 sqyon |
100 | 1.194 s | 0.32 MiB | C++ |
| 关于 寻找素数项 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
♂
| ||||
|
可以拿这题试各种素数判定算法……我用的是Rabin_Miller测试
| ||||
【题目描述】
设数列{an}满足如下递推式：
ai=(ai-1+1234567890) mod 2^31，其中i>=2.
给定a1，判断a1，a2，...，a100000是否是素数。若是输出1，否则输出0。
【输入格式】
一行一个正整数a1，在int范围内。
【输出格式】
一行，一个长度为100000的01串。第i项个字符对应ai是否为素数。若是则为1，不是则为0。
【样例输入】
1
【样例输出】
答案串的前50项为：
01000000000000000000000000001000010000000001100000
【提示】
这里的输入输出格式和SPOJ上原题不同。
数列的第一项为1（非素数），第二项为1234567891（素数），以此类推。