Editorial for Bedao Regular Contest 03 - 3 NUMBERS


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Không mất tính tổng quát, giả sử là ~a \le b \le c~.

Từ đây ta suy ra ~a \times a \times a \le n <=> a \le \sqrt[3]{n}~

Và từ ~a \times b \times c \le n~ ta suy ra ~b \times c \le \frac{n}{a} (1)~

Lại có ~a~ là số nguyên dương nên ~a \ge 1~ suy ra ~\frac{1}{a} \le 1 (2)~

Từ ~(1)~ và ~(2)~ suy ra ~b \times b \le b \times c \le \frac{n}{a} \le n~

~=> b \le \sqrt{n}~

Từ đây, ta tính được số bộ ~3~ số ~(a,b,c)~ với ~a \le b \le c~ và ~a \times b \times c \le n~

Gọi kết quả vừa tính được là ~x~

Kết quả cuối cùng bằng ~x \times 6~ rồi trừ đi số lượng số bộ ~(a,b,c)~ bị lặp lại (tức là số bộ số mà ~a=b~ hoặc ~b=c~ hoặc ~c=a~ hoặc ~a=b=c~)

Code mẫu

#include <iostream>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <math.h>
#include <map>
#include <algorithm>
#include <set>
#include <bitset>
#include <queue>
#include <cstring>
#include <stack>
#include <iomanip>
#include <assert.h>

#define BIT(x,pos) (((x)>>(pos)) & 1LL)
#define _(x) (1LL<<(x))
#define bitCnt(x) __builtin_popcountll(x)
#define turnOn(x,pos) ((x) = (_(pos)))
#define turnOff(x,pos) ((x) &= ~(_(pos)))
#define flipBit(x,pos) ((x) ^= (_(pos)))
#define lowBit(x) ((x) & (-x))
#define turnAll(x) (_(x)-1LL)

#define int long long
#define name "test"
#define nameTask ""
#define fastIO ios::sync_with_stdio(false); cin.tie(0);

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;

signed main()
{
    fastIO

    int n;
    cin>>n;

    ll cnt = 0;
    for (ll i = 1;i <= trunc(sqrt(n)); ++i)
        for (ll j = i + 1;j*j*i <= n; ++j)
        {
            int x = n / i / j;
            cnt += ((x-j) > 0 ? x - j : 0) * 6;
        }

    for (int i = 1;i <= trunc(sqrt(n)); ++i)
    {
        int x = n / i / i;
        if (x >= i) --x;
        cnt += x * 3;
    }

    for (ll i = 1; i*i*i <= n; ++i) ++cnt;

    cout<<cnt;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.