BZOJ3813 奇数国

2015.01.13 09:46 Tue| 0 visits oi_2015| 2015_刷题日常| Text

Problem

绝对有必要澄清这道语文题的题意:

有 10W 个数,保证其中每一个数都可以分解成前 60 个素数的乘积,每一次询问其中一段数的乘积的欧拉函数值,答案对 19961993 素数取模。

Solution

很简单,线段树维护乘积和利用 bitset 保存的这一乘积中含有的素因数,每一次询问直接利用逆元求欧拉函数即可。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 100005
#define P 19961993
#define lson (pos << 1)
#define rson (pos << 1 | 1)

inline int read()
{
    int x=0, f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); }
    return x*f;
}

bitset<61> bits[N << 2];
int n, tot, inv[282], mapp[282], prime[282], sum[N << 2];

inline bool check(int x)
{
    for (int i = 2; i * i <= x; ++i)
        if(x % i == 0) return false;
    return true;
}

void getprime()
{
    inv[1] = 1;
    for (int i = 2; i <= 281; ++i)
    {
        inv[i] = (long long)(P - P/i) * inv[P % i] % P;
        if (check(i)) prime[mapp[i] = ++tot] = i;
    }
}

inline bitset<61> getbits(int x)
{
    bitset<61> re;
    for (int i = 1; i <= 60; ++i)
        if (x % prime[i] == 0)
            re[i]= 1;
    return re;
}

void build(int pos, int l, int r)
{
    if (l == r)
    {
        bits[pos][2] = 1; sum[pos] = 3;
        return ;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    bits[pos] = bits[lson] | bits[rson];
    sum[pos] = (long long)sum[lson] * sum[rson] % P;
}

void modify(int pos, int l, int r, int x, int y)
{
    if (l == x && r == x)
    {
        bits[pos] = getbits(y); sum[pos] = y;
        return ;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y);
    else modify(rson, mid + 1, r, x, y);
    bits[pos] = bits[lson] | bits[rson];
    sum[pos] = (long long)sum[lson] * sum[rson] % P;
}

pair<bitset<61>, int> query(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return make_pair(bits[pos], sum[pos]);
    int mid = (l + r) >> 1;
    pair<bitset<61>, int> ansl(0, 1), ansr(0, 1);
    if (x <= mid) ansl = query(lson, l, mid, x, y);
    if (y > mid) ansr = query(rson, mid + 1, r, x, y);
    return make_pair(ansl.first | ansr.first,
                     (long long)ansl.second * ansr.second % P);
}

int main()
{
    cin >> n;
    getprime();
    build(1, 1, N);
    for (int i = 1; i <= n; ++i)
    {
        int opt = read(), x = read(), y = read();
        if (opt)
            modify(1, 1, N, x, y);
        else
        {
            pair<bitset<61>, int> ans = query(1, 1, N, x, y);
            for (int j = 1; j <= 60; ++j)
                if (ans.first[j])
                    ans.second = 1LL * ans.second * inv[prime[j]] % P,
                    ans.second = 1LL * ans.second * (prime[j] - 1) % P;
            printf("%d\n", ans.second);
        }
    }
    return 0;
}