### VIRUSGAMING's blog

By VIRUSGAMING, history, 5 months ago,

### Hi codeforces.

Today i meet the problem that calculate:

$\displaystyle\sum_{i=1}^{n}\frac{n}{gcd(i,n)}$

and n <= 1e7 and have 1e6 testcase with n

$\displaystyle\sum_{i=1}^{n}\frac{n}{gcd(i,n)} = \displaystyle\sum_{i=1}^{m}t_{i} * \phi{(t_{i})}$

with $t_{i}$ is divisor of n and $\phi{(t_{i})}$ is euler totient function. Help me to make it fast and can run 1s on codeforces. Thanks for your help.

• +10

By VIRUSGAMING, history, 9 months ago,

The segment tree is a very useful algorithm when doing many RMQ problems, we have the following problem: https://mirror.codeforces.com/contest/1199/problem/D how to solve it? Well, here is the segment tree to help us, but what is the segment tree? Well, it is a tree where each node is F(x, y) being x and y stored in its 2 children here is an example and the implementation:

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef LOCAL
#include "debug/debug.h"
#include "float/floatx.hpp"
#include "ttmath/ttmath.h"
#include "json/json.hpp"
#include <omp.h>
#include <unistd.h>
#include <windows.h>
using namespace flx;
using namespace ttmath;
using namespace nlohmann;
using namespace literals;
#include "win/api.hpp"
#endif
#ifndef LOCAL
#define debug
#endif
#define pb push_back
#define ll long long
#define ld long double
#define fx ld // antes estaba otra cosa
#define ull unsigned ll
#define S second
#define F first
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
#define MOD 1000000007
const ll INF = 1e18, MAXN = 5e5 + 10;

typedef tree<ll, null_type, less_equal<ll>,
rb_tree_tag, tree_order_statistics_node_update>
TREE;

ll a[MAXN], st[MAXN * 4], lazy[MAXN * 4];

ll F(ll a, ll b)
{
return a + b;
}

void build(ll n, ll l, ll r)
{
lazy[n] = 0;
if (l == r)
{
st[n] = a[l];
return;
}
ll m = (l + r) / 2;
build(n * 2, l, m);
build(n * 2 + 1, m + 1, r);
st[n] = F(st[n * 2], st[n * 2 + 1]);
}

void prop(ll l, ll r, ll n)
{
st[n] += lazy[n] * (r - l + 1);
if (l != r)
{
lazy[n * 2] = lazy[n];
lazy[n * 2 + 1] = lazy[n];
}
lazy[n] = 0;
}

void update(ll n, ll l, ll r, ll a, ll b, ll val)
{
prop(l, r, n);
if (l > b || r < a)
return;
if (l >= a && r <= b)
{
lazy[n] += val;
prop(l, r, n);
return;
}
ll m = (l + r) / 2;
update(n * 2, l, m, a, b, val);
update(n * 2 + 1, m + 1, r, a, b, val);
st[n] = F(st[n * 2], st[n * 2 + 1]);
}

ll query(ll n, ll l, ll r, ll a, ll b)
{
prop(l, r, n);
if (l > b || r < a)
return 0;
if (l >= a && r <= b)
return st[n];
ll m = (l + r) / 2;
ll q1 = query(n * 2, l, m, a, b);
ll q2 = query(n * 2 + 1, m + 1, r, a, b);
return F(q1, q2);
}

int main(){
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
build(1,1,n);
int q;
cin >> q;
while(q--){
//process query
}
}

• -9

By VIRUSGAMING, history, 11 months ago,

from what I understand in this code the pointer p points to memory address 0x64ff but when trying to put a value there gives runtime error how to solve that problem? I know this has nothing to do with competitive, sorry

#pragma GCC Optimize("Ofast", "O2")
#pragma GCC target("avx2", "avx")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef LOCAL
#include <windows.h>
#endif
#define Tree tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define INF 1LL << 62
#define ll long long
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;

int* p = (int*)(0x64ff);

signed main()
{
}


• -6

By VIRUSGAMING, history, 11 months ago,

Hello, I would like to know if the user: chappy1 is a bot, if not, how can I do so many problems in 1 month?

• -19