[洛谷题单]欧拉函数与欧拉定理

P1082 同余方程
就是一个裸的 exgcd，没了。
顺便也当板子存起来（

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
ll a, b, x, y;
void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a
    ll t = x;
    x = y;
    y = t - a / b * y;
}
inline void solve()
{
    cin >> a >> b;
    exgcd(a, b, x, y);
    x = ((x
    cout << x << endl;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

P2613 【模板】有理数取余
你看题目中就有一个【模板】这两个字，那就肯定是个模板了......
嘛，也当成板子存下来吧（

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used:
    system("pause");
#endif
}
template <class T>
inline void read(T &x)
{
    bool f = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = 1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        x
        ch = getchar();
    }
    if (f)
        x = -x;
}
ll a, b, x, y;
void exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a
    ll t = x;
    x = y;
    y = t - a / b * y;
}
inline ll getinv(ll a, ll mod2)
{
    ll x = 0, y = 0;
    exgcd(a, mod2, x, y);
    x = (x
    return x;
}
inline void solve()
{
    read(a), read(b);
    if (__gcd(b, 19260817ll) > 1)
        return puts("Angry!"), void();
    ll invb = getinv(b, 19260817ll);
    cout << a * invb
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

P2158 [SDOI2008]仪仗队
这题也是非常经典的了
如果设原点是 $(0,0)$，那么只有 $\gcd(i,j)==1$ 的那些人才会被看到，因为之后的人就被他挡住了。
于是答案就是
$$
\begin{eqnarray}
& 1+2\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{i}[\gcd(i,j)==1] \\
& = 1+2\sum\limits_{i=1}^{n-1}\varphi(i)
\end{eqnarray}
$$
然后这个就是 $\mathcal{O}(n)$ 的。当然要搞事的话后面那个也可以用杜教筛去做（比如我）。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <cstdlib>
#include <ctime>
#include <string>
#include <queue>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 250;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\nTime used:
    system("pause");
#endif
}
bool vis[N];
ll tot, pri[N], mu[N], sum_mu[N], sum_phi[N], phi[N];
map<ll, ll> visphi, vismu;
inline void shaipri(int lim)
{
    phi[1] = mu[1] = 1;
    for (int i = 2; i < lim; ++i)
    {
        if (!vis[i])
            vis[i] = 1, pri[++tot] = i, mu[i] = -1, phi[i] = i - 1;
        for (int j = 1; j <= tot && i * pri[j] < lim; ++j)
        {
            vis[i * pri[j]] = 1;
            if (i
            {
                mu[i * pri[j]] = -mu[i];
                phi[i * pri[j]] = phi[i] * (pri[j] - 1);
            }
            else
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                mu[i * pri[j]] = 0;
                break;
            }
        }
    }
}
int n;
ll solvemu(ll x)
{
    if (vismu[x])
        return vismu[x];
    if (x < N)
        return sum_mu[x];
    ll ret = 1;
    for (int l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        ret -= (r - l + 1ll) * solvemu(x / l);
    }
    return vismu[x] = ret;
}
ll solvephi(ll x)
{
    if (visphi[x])
        return visphi[x];
    if (x < N)
        return sum_phi[x];
    ll ret = x * (x + 1) / 2;
    for (int l = 2, r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        ret -= (r - l + 1ll) * solvephi(x / l);
    }
    return visphi[x] = ret;
}
inline void solve()
{
    scanf(
    if (n==0)return puts("0"),void();
//    ll ansmu = solvemu(n);
    ll ansphi = solvephi(n);
    printf(
}
int main()
{
    TIME__START = clock();
    shaipri(N);
    for (int i = 1; i < N; ++i)
        sum_mu[i] = sum_mu[i - 1] + mu[i], sum_phi[i] = sum_phi[i - 1] + phi[i];
    int Test = 1;
//    scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

未完待续

[洛谷题单]欧拉函数与欧拉定理

Codeforces Round #667(Div.3) 解题报告

[atcoder abc179]解題報告

Comments NOTHING

取消回复