NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #213290 | #3850. 因子数列 | Anthonyyan | 5 | 82ms | 1284kb | C++ | 1.1kb | 2024-11-10 12:30:50 | 2024-11-10 13:07:17 |
answer
#include <bits/stdc++.h>
#define MOD 998244353
using namespace std;
int gcd(int a, int b)
{
return __gcd(a, b);
}
vector<int> get_factors(int m)
{
vector<int> factors;
for (int i = 1; i <= sqrt(m); ++i)
if (m % i == 0)
{
factors.push_back(i);
if (i != m / i)
factors.push_back(m / i);
}
return factors;
}
int solve(int n, int m)
{
vector<int> factors = get_factors(m);
int k = factors.size();
vector<int> factor_index(k);
for (int i = 0; i < k; ++i)
factor_index[i] = factors[i];
vector< vector<int> >
dp(n + 1, vector<int>(k, 0));
for (int j = 0; j < k; ++j)
dp[1][j] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 0; j < k; ++j)
for (int l = 0; l < k; ++l)
if (gcd(factors[l], factors[j]) > 1)
dp[i][j] = (dp[i][j] + dp[i - 1][l]) % MOD;
int result = 0;
for (int j = 0; j < k; ++j)
result = (result + dp[n][j]) % MOD;
return result;
}
int main()
{
int n, m,
T;
cin >> m >> T;
while (T--)
{
cin >> n;
cout << solve(n, m) << endl;
}
return 0;
}
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 82ms
memory: 1284kb
input:
210 200 113 296 253 65 203 145 64 55 50 77 43 251 260 55 156 265 297 230 119 294 120 42 208 243 269 ...
output:
935976218 343912335 649383706 70777499 656212177 589866733 12591199 904255419 459054665 956167638 43...
result:
ok 200 numbers
Test #2:
score: 0
Dangerous Syscalls
input:
252 1 314055503869010724
output:
result:
Test #3:
score: 0
Dangerous Syscalls
input:
282 1 264777687269675469
output:
result:
Test #4:
score: 0
Dangerous Syscalls
input:
290 200 802726718582470993 513758619815309942 189274088962622536 860983948867274839 3577502703482725...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
58198140 200 959 862 510 520 426 547 672 141 111 147 520 962 909 302 854 306 934 524 733 649 886 695...
output:
result:
Test #6:
score: 0
Dangerous Syscalls
input:
62180118 1 926181104898054637
output:
result:
Test #7:
score: 0
Dangerous Syscalls
input:
95611230 1 182274277242753806
output:
result:
Test #8:
score: 0
Dangerous Syscalls
input:
95233320 200 345690473651689621 377192517307333764 491266035915286354 277537088705458756 69755658847...
output:
result:
Test #9:
score: 0
Dangerous Syscalls
input:
85765680 200 842604215470675913 693968348917184945 194347127230511886 923041766224662131 52394950648...
output:
result:
Test #10:
score: 0
Wrong Answer
time: 0ms
memory: 1156kb
input:
802241960520 1 337589677349356513
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
Test #11:
score: 0
Wrong Answer
time: 0ms
memory: 1156kb
input:
644348954340 1 130986907629009228
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 1156kb
input:
705537072240 1 267882780122683404
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
Test #13:
score: 0
Wrong Answer
time: 0ms
memory: 1156kb
input:
776363187600 200 106688853771652749 752427214283496810 586926336522723525 681973907945298011 6448233...
output:
result:
wrong answer Answer contains longer sequence [length = 200], but output contains 0 elements
Test #14:
score: 0
Wrong Answer
time: 0ms
memory: 1152kb
input:
694247850450 200 465336166247569990 734514969437137822 774584419214433387 636222504876595962 7302379...
output:
result:
wrong answer Answer contains longer sequence [length = 200], but output contains 0 elements
Test #15:
score: 0
Wrong Answer
time: 0ms
memory: 1156kb
input:
9127507905816300 1 934417805794906683
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
Test #16:
score: 0
Wrong Answer
time: 0ms
memory: 1156kb
input:
8265306123944870 1 140182875145542025
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
Test #17:
score: 0
Wrong Answer
time: 0ms
memory: 1160kb
input:
8217027977558400 1 176919885071352138
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
Test #18:
score: 0
Wrong Answer
time: 0ms
memory: 1156kb
input:
9390889117209600 1 210913601057588245
output:
result:
wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
Test #19:
score: 0
Wrong Answer
time: 0ms
memory: 1160kb
input:
6775660251360000 200 984345398232352633 978615808106577653 215878340541519263 332384616027183722 730...
output:
result:
wrong answer Answer contains longer sequence [length = 200], but output contains 0 elements
Test #20:
score: 0
Wrong Answer
time: 0ms
memory: 1160kb
input:
2869438341369600 200 461375240042131253 485682298432589970 179932945870690884 157449555540945918 910...
output:
result:
wrong answer Answer contains longer sequence [length = 200], but output contains 0 elements
