Submission #3305200


Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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) {
    short 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 4731 Byte
Status AC
Exec Time 2470 ms
Memory 23712 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 829 ms 22168 KB
02.txt AC 2261 ms 22168 KB
03.txt AC 644 ms 22168 KB
04.txt AC 1856 ms 22168 KB
05.txt AC 1013 ms 22168 KB
06.txt AC 2470 ms 23712 KB
07.txt AC 907 ms 22168 KB
08.txt AC 2341 ms 22168 KB
09.txt AC 498 ms 22168 KB
10.txt AC 1393 ms 22168 KB
11.txt AC 432 ms 22168 KB
12.txt AC 816 ms 23712 KB
13.txt AC 268 ms 21912 KB
14.txt AC 468 ms 21784 KB
15.txt AC 269 ms 22040 KB
16.txt AC 470 ms 21912 KB
17.txt AC 1115 ms 22168 KB
18.txt AC 2255 ms 22168 KB
19.txt AC 815 ms 22296 KB
20.txt AC 1587 ms 22168 KB
21.txt AC 381 ms 22168 KB
22.txt AC 716 ms 22168 KB
s1.txt AC 50 ms 19584 KB
s2.txt AC 49 ms 19584 KB