QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#718239 | #8980. Prime Game | liaoyd | WA | 8ms | 7452kb | C++23 | 1.8kb | 2024-11-06 20:02:49 | 2024-11-06 20:02:49 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define vii vector<vi>
#define pb push_back
#define pir pair<int, int>
const int P = 1e9 + 7;
const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f; // longlong
const int ing = 1e18;
// const int mod = 998244353;
// cout << fixed << setprecision(5) << number << endl;
// tuple
// prev(it) next(it)
const int mod = 1e9 + 7;
int n, m;
int ax, bx, ay, by;
bool st[N];
int pr[N];
void get(int n)
{
for (int i = 2; i <= 1e6; i++)
{
if (!st[i])
{
pr[++pr[0]] = i;
}
for (int j = 1; pr[j] <= 1e6 / i; j++)
{
st[pr[j] * i] = 1;
if (pr[j] % i == 0)
break;
}
}
st[1] = 1;
}
void solve()
{
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
get(N);
map<int, int> mp;
int ans = 0;
for (int i = 1; i <= n; i++)
{
ax = a[i];
for (int j = 1; pr[j] <= ax; j++)
{
if (!st[ax])
{
if (!mp[ax])
mp[ax] = -1;
// cout<<ax<<"\n";
ans += (n - i) * (i - mp[ax]);
mp[ax] = i;
break;
}
if (ax % pr[j] == 0)
{
while (ax % pr[j] == 0) ax /= pr[j];
if (!mp[pr[j]]) mp[pr[j]] = -1;
ans += (n - i) * (i - mp[pr[j]]);
mp[pr[j]] = i;
//cout<<pr[j]<<"\n";
}
}
}
cout << ans << "\n";
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
int _ = 1;
// cin >> _;
while (_--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 7452kb
input:
10 99 62 10 47 53 9 83 33 15 24
output:
248
result:
ok single line: '248'
Test #2:
score: -100
Wrong Answer
time: 8ms
memory: 5380kb
input:
10 6 7 5 5 4 9 9 1 8 12
output:
141
result:
wrong answer 1st lines differ - expected: '134', found: '141'