谁告诉我这东西怎么翻译成英文啊(躺
照例备份代码

51nod 1244

#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
const int maxpow = 4641600, MOD = 23333;
struct N{long long v, w; N *n;} *h[MOD];
int powb;
bool v[maxpow];
int p[413000], pc = 0; 
long long m[maxpow], u[maxpow];
long long Mu(long long n)
{
    if(n <= powb) return u[n];
    for(N *i = h[n % MOD]; i; i = i->n) if(i->v == n)
        return i->w;
    long long ret = 1;
    for(long long st = 2, en; st <= n; st = en + 1)
        en = n / (n / st), ret -= (en - st + 1) * Mu(n / st);
    h[n % MOD] = new N {n, ret, h[n % MOD]}; 
    return ret;
}
int main()
{
    long long a, b; read(a, b);
    powb = ceil(pow(b, 2.0 / 3.0));
    u[1] = 1;
    for(int i = 2; i <= powb; i++)
    {
        if(!v[i]) p[pc++] = i, m[i] = -1, v[i] = true;
        for(int j = 0; i * p[j] <= powb; j++)
            if(i % p[j]) m[i * p[j]] = -m[i], v[i * p[j]] = true;
            else {m[i * p[j]] = 0; v[i * p[j]] = true; break;}
        u[i] = u[i - 1] + m[i];
    }
    printf("%lld\n", Mu(b) - Mu(a - 1));
    return 0;
}

BZOJ 3944 103364 kb 10228 ms
mgj预处理数组上限打小了t到怀疑人生

#include <cstdio>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
const int maxpow = 4641600, MOD = 23333;
struct N{long long v, w; N *n;} *h[MOD];
int powb;
bool v[maxpow];
int p[413000], pc = 0; 
long long m[maxpow], u[maxpow];
long long Mu(long long n)
{
    if(n <= powb) return u[n];
    for(N *i = h[n % MOD]; i; i = i->n) if(i->v == n)
        return i->w;
    long long ret = 1;
    for(long long st = 2, en; st <= n; st = en + 1)
        en = n / (n / st), ret -= (en - st + 1) * Mu(n / st);
    h[n % MOD] = new N {n, ret, h[n % MOD]}; 
    return ret;
}
int main()
{
    long long a, b; read(a, b);
    powb = ceil(pow(b, 2.0 / 3.0));
    u[1] = 1;
    for(int i = 2; i <= powb; i++)
    {
        if(!v[i]) p[pc++] = i, m[i] = -1, v[i] = true;
        for(int j = 0; i * p[j] <= powb; j++)
            if(i % p[j]) m[i * p[j]] = -m[i], v[i * p[j]] = true;
            else {m[i * p[j]] = 0; v[i * p[j]] = true; break;}
        u[i] = u[i - 1] + m[i];
    }
    printf("%lld\n", Mu(b) - Mu(a - 1));
    return 0;
}

BZOJ 4805 75852 kb 12348 ms

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int pow23 = 1600000, mod = 233333;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
map<int, long long> P;
long long Phi(long long n)
{
    if(P[n]) return P[n];
    long long ret = (n * n + n) / 2;
    for(long long st = 2, en; st <= n; st = en + 1)
    {
        en = n / (n / st);
        ret -= (en - st + 1) * Phi(n / st);
    }
    return P[n] = ret;
}
long long p[pow23 + 1], pc = 0, q[pow23 + 1];
int main()
{
    long long n; read(n);
    P[1] = q[1] = 1;
    for(int i = 2; i <= pow23; i++)
    {
        if(!q[i]) p[pc++] = i, q[i] = i - 1;
        for(int j = 0; i * p[j] <= pow23; j++)
            if(i % p[j]) q[i * p[j]] = q[i] * (p[j] - 1);
            else{q[i * p[j]] = q[i] * p[j]; break;}
        P[i] = P[i - 1] + q[i];
    }
    printf("%lld\n", Phi(n));
    return 0;
}

标签: none

添加新评论