Cod sursa(job #3166934)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 9 noiembrie 2023 19:31:19
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#ifndef LOCAL
    #pragma GCC optimize("Ofast")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define int long long

#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const int NMAX = 1e6 + 5;
/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("mins.in");
    ofstream out("mins.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

int N, M;
ll rasp;
bool ciur[NMAX];
int dp[NMAX], mobius[NMAX];
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> N >> M;

    N --; M --;
    if (N > M)
        swap(N, M);
}
///-------------------------------------
inline void Solution()
{
    for (int i = 1 ; i <= N ; ++ i) mobius[i] = 1;

    int mult;
    for (int i = 2 ; i <= N ; ++ i)
    {
        if (!ciur[i])
        {
            for (int j = 2 * i ; j <= N ; j += i)
            {
                mobius[j] *=  (-1);
                ciur[j] = true;
            }

            ll ii = i * i;
            for (ll j = ii ; j <= N ; j += ii)
            {
                mobius[j] = 0;
            }
        }

        if (!mobius[i]) continue;

        mult = M / i;
        for (int j = i ; j <= N ; j += i)
        {
            dp[j] += mobius[j] * mult;
        }
    }

    for (int i = 1 ; i <= N ; ++ i)
    {
        rasp += 1LL * (M - dp[i]);
    }
}
///-------------------------------------
inline void Output()
{
    cout << rasp;
}
///-------------------------------------
signed main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}