Submission #3305193
Source Code Expand
#include <bits/stdc++.h>
#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 |
4619 Byte |
Status |
AC |
Exec Time |
2469 ms |
Memory |
22168 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1100 / 1100 |
Status |
|
|
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 |
733 ms |
22168 KB |
02.txt |
AC |
2086 ms |
22168 KB |
03.txt |
AC |
611 ms |
22168 KB |
04.txt |
AC |
1794 ms |
22168 KB |
05.txt |
AC |
944 ms |
22168 KB |
06.txt |
AC |
2469 ms |
22168 KB |
07.txt |
AC |
797 ms |
22168 KB |
08.txt |
AC |
2108 ms |
22168 KB |
09.txt |
AC |
459 ms |
22168 KB |
10.txt |
AC |
1197 ms |
22168 KB |
11.txt |
AC |
437 ms |
22168 KB |
12.txt |
AC |
840 ms |
22168 KB |
13.txt |
AC |
268 ms |
21912 KB |
14.txt |
AC |
489 ms |
21784 KB |
15.txt |
AC |
270 ms |
22040 KB |
16.txt |
AC |
491 ms |
21912 KB |
17.txt |
AC |
1094 ms |
22168 KB |
18.txt |
AC |
2230 ms |
22168 KB |
19.txt |
AC |
779 ms |
22168 KB |
20.txt |
AC |
1535 ms |
22168 KB |
21.txt |
AC |
353 ms |
22168 KB |
22.txt |
AC |
667 ms |
22168 KB |
s1.txt |
AC |
49 ms |
19584 KB |
s2.txt |
AC |
49 ms |
19584 KB |