VIRUSGAMING's blog

By VIRUSGAMING, history, 14 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it

By VIRUSGAMING, history, 18 months ago, In English

The segment tree is a very useful algorithm when doing many RMQ problems, we have the following problem: https://codeforces.net/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 THREAD_NUM 32
#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 
    }
}

Full text and comments »

  • Vote: I like it
  • -9
  • Vote: I do not like it

By VIRUSGAMING, history, 19 months ago, In English

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()
{
}

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

By VIRUSGAMING, history, 19 months ago, In English

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?

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it