| 题目名称 | 2180. 无关的数 |
|---|---|
| 输入输出 | irre.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 mouse
于2016-03-16加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：27， 通过率：44.44% | ||||
 Zayin |
100 | 0.041 s | 0.50 MiB | C++ |
 zhengtn03 |
100 | 0.045 s | 1.08 MiB | C++ |
 @@@ |
100 | 0.046 s | 40.22 MiB | C++ |
 APWTMECRD |
100 | 0.052 s | 1.20 MiB | C++ |
 Ceres |
100 | 0.064 s | 1.43 MiB | C++ |
 サイタマ |
100 | 0.065 s | 36.19 MiB | C++ |
 Benjamin |
100 | 0.089 s | 0.70 MiB | C++ |
 Fmuckss |
100 | 0.104 s | 0.70 MiB | C++ |
|
zhengtn03 |
100 | 0.109 s | 1.08 MiB | C++ |
 烟雨 |
100 | 0.110 s | 0.76 MiB | C++ |
| 本题关联比赛 | |||
| 20160316 | |||
| 关于 无关的数 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Zayin :
唔...那样似乎复杂度更优一些? 我是n*log*gcd... Fmuckss
2016-03-21 10:19
6楼
| ||||
|
回复 @Fmuckss : 我是直接判断能否整除m的每一个因子…
| ||||
|
回复 @Zayin :
而且我把输出都优化了..郁闷...不过可能是算法上的问题...我见你们好像都没求gcd Fmuckss
2016-03-19 17:25
4楼
| ||||
|
回复 @Zayin :
不知道是什么问题...感觉我的常数很大...因为用的long long比较多...不用long long会出问题..本来打算记录m的次数和余数...但是后来嫌麻烦就直接伸手党了←_←... Fmuckss
2016-03-19 17:24
3楼
| ||||
|
回复 @Fmuckss : 难道是我常数写小了吗...
| ||||
|
求常数更小的算法
| ||||
【题目描述】
对于给定的n个数a1,a2,…,an，依次求出两邻两数之和，将得到一个新数列。重复上述操作，最后结果将变成一个数。问这个数除以m的余数与哪些数无关？例如n=3,m=2时，第一次求和得到a1+a2,a2+a3,再求和得到a1+2a2+a3，它除以2的余数和a2无关。
【输入格式】
输入有一行，两个整数n和m,其中1≤n≤10^5,2≤m≤10^9
【输出格式】
输出有两行，第一行为无关的数的个数，第二行为这些无关的数的下标。
【样例输入】
3 2
【样例输出】
1 2
【提示】
在此键入。
【来源】
在此键入。