Submission #3305194


Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

#define getchar getchar_unlocked
#define putchar putchar_unlocked

inline int in() {
    int n, c;
    while ((c = getchar()) < '0') if (c == EOF) return -1;
    n = c - '0';
    while ((c = getchar()) >= '0') n = n * 10 + c - '0';
    return n;
}

inline void out(int n) {
    int res[11], i = 0;
    do { res[i++] = n % 10, n /= 10; } while (n);
    while (i) putchar(res[--i] + '0');
    putchar('\n');
}

vi pr[MAX_N], id[MAX_N];
bool is_prime[MAX_N];

void all_fac()
{
    fill(is_prime,is_prime+MAX_N,true);
    for(int i=2;i<MAX_N;i++){
        if(is_prime[i]){
            pr[i].pb(i);
            id[i].pb(1);
            for(int j=2*i;j<MAX_N;j+=i){
                is_prime[j] = false;
                int cnt = 0;
                int nw = j;
                while(nw % i == 0){
                    nw /= i;
                    cnt++;
                }
                pr[j].pb(i);
                id[j].pb(cnt);
            }
        }
    }
}

int inv[20*MAX_N];

void make()
{
	inv[1] = 1;
	for(int i=2;i<20*MAX_N;i++){
		inv[i] = MOD - (ll)inv[MOD%i] * (MOD/i) % MOD;
	}
}

inline int add(int x,int y)
{
    return (x+y)%MOD;
}

inline int sub(int x,int y)
{
    return (x+MOD-y)%MOD;
}

inline int mul(int x,int y)
{
    return (ll)x*y%MOD;
}

int res;
int cnt[MAX_N], a[MAX_N];

class Mo{
private:
    vector<int> left, right;
    int w;
    void add(int id);
    void del(int id);

public:
    vector<int> ans;

    Mo(int n) : w(600){}
    //クエリ[l,r)
    void insert(int l, int r){
        left.push_back(l), right.push_back(r);
    }
    void solve(){
        int sz = (int)left.size();
        int nl = 0, nr = 0;
        vector<int> ord(sz);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int a, int b){
            return (left[a] / w == left[b] / w) ? (right[a] < right[b]) : (left[a] < left[b]);
        });
        ans.resize(sz);
        for(int i = 0; i < sz; i++){
            const int id = ord[i];  //order:クエリのsort後のorder→元のorder
            while(nl > left[id]) add(--nl);
            while(nr < right[id]) add(nr++);  //add
            while(nl < left[id]) del(nl++);
            while(nr > right[id]) del(--nr);  //del
            ans[id] = res;
        }
    }
};

//idは元の配列のインデックス
void Mo::add(int index)
{
    int num = a[index];
    rep(i, len(pr[num])){
        int& hoge = cnt[pr[num][i]];
        res = mul(res, inv[hoge]);
        hoge += id[num][i];
        res = mul(res, hoge);
    }
}

void Mo::del(int index)
{
    int num = a[index];
    rep(i, len(pr[num])){
        int& hoge = cnt[pr[num][i]];
        res = mul(res, inv[hoge]);
        hoge -= id[num][i];
        res = mul(res, hoge);
    }
}

int main()
{
    int n = in(), q = in();
    rep(i,n){
        a[i] = in();
    }
    make();
    all_fac();
    Mo mo(n);
    rep(i,q){
        int l = in(), r = in();
        mo.insert(l-1, r);
    }
    rep(i, MAX_N){
        cnt[i] = 1;
    }
    res = 1;
    mo.solve();
    rep(i,q){
        out(mo.ans[i]);
    }
    return 0;
}

Submission Info

Submission Time
Task B - ニワンゴくんの約数
User kopricky
Language C++14 (GCC 5.4.1)
Score 1100
Code Size 4674 Byte
Status AC
Exec Time 2387 ms
Memory 22296 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1100 / 1100
Status
AC × 2
AC × 24
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 704 ms 22168 KB
02.txt AC 2012 ms 22168 KB
03.txt AC 567 ms 22168 KB
04.txt AC 1654 ms 22168 KB
05.txt AC 909 ms 22168 KB
06.txt AC 2387 ms 22296 KB
07.txt AC 764 ms 22168 KB
08.txt AC 2046 ms 22168 KB
09.txt AC 442 ms 22168 KB
10.txt AC 1150 ms 22168 KB
11.txt AC 416 ms 22168 KB
12.txt AC 784 ms 22168 KB
13.txt AC 247 ms 21912 KB
14.txt AC 434 ms 21784 KB
15.txt AC 247 ms 22040 KB
16.txt AC 437 ms 21912 KB
17.txt AC 1072 ms 22168 KB
18.txt AC 2167 ms 22168 KB
19.txt AC 757 ms 22168 KB
20.txt AC 1488 ms 22168 KB
21.txt AC 332 ms 22168 KB
22.txt AC 616 ms 22168 KB
s1.txt AC 50 ms 19584 KB
s2.txt AC 50 ms 19584 KB