Contest Duration: - (local time) (110 minutes) Back to Home

Submission #7643710

Source Code Expand

Copy
```#ifdef DBG1
#define LOCAL
#endif

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#ifdef DBG1
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
#define dbg(...)
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

const int P = 998244353;

int diff(int a, int b) {
if ((a -= b) < 0) {
a += P;
}
return a;
}

int sum(int a, int b) {
if ((a += b) >= P) {
a -= P;
}
return a;
}

int &add(int &a, int b) {
return a = sum(a, b);
}

int &subtract(int &a, int b) {
return a = diff(a, b);
}

int prod(int a, int b) {
return int(ll(a) * b % P);
}

int power(int a, int n) {
int b = 1;
while (n) {
if (n & 1) {
b = prod(a, b);
}
a = prod(a, a);
n /= 2;
}
return b;
}

int inverse(int a) {
return power(a, P - 2);
}

void update(int &ans, vector<int> &sum, const vector<int> &factor, int a, int d) {
}

bool solve() {
int n;
if (scanf("%d", &n) != 1) { return false; }
vector<int> a(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}

const int MAX = *max_element(a.begin(), a.end());

vector<int> prime_div(MAX + 1);
for (int i = 2; i <= MAX; ++i) {
if (prime_div[i] == 0) {
for (int j = i; j <= MAX; j += i) {
prime_div[j] = i;
}
}
}

vector<int> factor(MAX + 1);
for (int i = 1; i <= MAX; ++i) {
factor[i] = inverse(i);
}
/*for (int i = 1; i <= MAX; ++i) {
for (int d = 1; d * d <= i; ++d) {
if (i % d == 0) {
if (d != i) {
subtract(factor[i], factor[d]);
}
int d2 = i / d;
if (d2 != d && d2 != i) {
subtract(factor[i], factor[d2]);
}
}
}
if (MAX <= 10) {
dbg("factor[%d] = %d\n", i, factor[i]);
}
}*/
//for (int i = 1; i <= MAX; ++i) {
for (int i = MAX; i >= 1; --i) {
vector<int> primes;
for (int x = i; x > 1; ) {
int p = prime_div[x];
primes.push_back(p);
//        subtract(factor[i], prod(1, factor[i / p]));
assert(x % p == 0 && p > 1);
while (x % p == 0) {
x /= p;
}
}

int k = int(primes.size());
int pr = 1, sign = 1;
for (int j = 0; j < k; ++j) {
if (mask & (1 << j)) {
pr *= primes[j];
sign = P - sign;
}
}
//dbg("factor[%d] += %d * factor[%d]\n", i, sign, i / pr);
}

if (MAX <= 10) {
dbg("factor[%d] = %d\n", i, factor[i]);
}
}

if (MAX <= 100) {
int total = 0;
for (int i = 1; i <= MAX; ++i) {
int sum = 0;
for (int d = 1; d <= i; ++d) {
if (i % d == 0) {
total++;
}
}
//dbg("%d: %d != %d\n", i, sum, inverse(i));
assert(sum == inverse(i));
}
dbg("total %d\n", total);
}

int ans = 0;
vector<int> sum(MAX + 1);
for (int i = 0; i < n; ++i) {
for (int d = 1; d * d <= a[i]; ++d) {
if (a[i] % d == 0) {

update(ans, sum, factor, a[i], d);
int d2 = a[i] / d;
if (d2 != d) {
update(ans, sum, factor, a[i], d2);
}
}
}
}
printf("%d\n", ans);

return true;
}

int main() {
int tt = -1;
//scanf("%d", &tt);
while (tt-- && solve());
return 0;
}
```

#### Submission Info

Submission Time 2019-09-21 22:44:53+0900 C - LCMs Kurpilyansky C++14 (GCC 5.4.1) 700 3773 Byte AC 1125 ms 14848 KB

#### Compile Error

```./Main.cpp: In function ‘bool solve()’:
./Main.cpp:86:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
^
```

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
 AC × 3
 AC × 21
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, sample-01.txt, sample-02.txt, sample-03.txt
Case Name Status Exec Time Memory
01-01.txt AC 355 ms 11264 KB
01-02.txt AC 662 ms 12416 KB
01-03.txt AC 841 ms 12672 KB
01-04.txt AC 379 ms 11904 KB
01-05.txt AC 785 ms 12544 KB
01-06.txt AC 605 ms 12288 KB
01-07.txt AC 520 ms 12160 KB
01-08.txt AC 718 ms 12544 KB
01-09.txt AC 555 ms 12160 KB
01-10.txt AC 871 ms 12800 KB
01-11.txt AC 936 ms 12800 KB
01-12.txt AC 864 ms 12800 KB
01-13.txt AC 930 ms 14848 KB
01-14.txt AC 878 ms 12800 KB
01-15.txt AC 930 ms 12800 KB
01-16.txt AC 871 ms 12800 KB
01-17.txt AC 933 ms 12800 KB
01-18.txt AC 1125 ms 12800 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB
sample-03.txt AC 333 ms 10624 KB