Submission #3708300
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define B 316
struct que{
ll l,r,i;
bool operator<(const que&q)const{
if(l!=q.l)return l<q.l;
return r<q.r;
}
};
ll n,q,inv[2000000],s,t[100005],ans[100005];
que m[100005];
vector<P>p[100005];
void up(ll v){
for(int i=0;i<p[v].size();i++){
ll x=p[v][i].F,y=p[v][i].S;
s=s*(t[x]+y+1)%M*inv[t[x]+1]%M;
t[x]+=y;
}
}
void ers(ll v){
for(int i=0;i<p[v].size();i++){
ll x=p[v][i].F,y=p[v][i].S;
s=s*(t[x]-y+1)%M*inv[t[x]+1]%M;
t[x]-=y;
}
}
int main(void){
scanf("%lld%lld",&n,&q);
inv[1]=1;
for(ll i=2;i<=20*n;i++)inv[i]=M-(M/i)*inv[M%i]%M;
for(int i=0;i<n;i++){
ll x;
scanf("%lld",&x);
for(ll j=2;j*j<=x;j++){
if(x%j==0){
p[i].PB(P(j,0));
while(x%j==0)x/=j,p[i].back().S++;
}
}
if(x!=1)p[i].PB(P(x,1));
}
for(int i=0;i<q;i++){
scanf("%lld%lld",&m[i].l,&m[i].r);
m[i].l--,m[i].r--,m[i].i=i;
}
sort(m,m+q);
ll e=0,w=B,a=0,b=0;
s=1,up(0);
while(e<q){
vector<que>o;
while(e<q&&m[e].l<w)o.PB(que{m[e].r,m[e].l,m[e].i}),e++;
sort(o.begin(),o.end());
for(int i=0;i<o.size();i++){
ll r=o[i].l,l=o[i].r;
while(l<a)up(--a);
while(r<b)ers(b--);
while(b<r)up(++b);
while(a<l)ers(a++);
ans[o[i].i]=s;
}
w+=B;
}
for(int i=0;i<q;i++)printf("%lld\n",ans[i]);
}
Submission Info
Submission Time |
|
Task |
B - ニワンゴくんの約数 |
User |
nxteru |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1481 Byte |
Status |
RE |
Exec Time |
2527 ms |
Memory |
37672 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:35:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&n,&q);
^
./Main.cpp:40:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&x);
^
./Main.cpp:50:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld",&m[i].l,&m[i].r);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
248 ms |
30100 KB |
02.txt |
AC |
1324 ms |
29568 KB |
03.txt |
AC |
247 ms |
28332 KB |
04.txt |
AC |
1052 ms |
27776 KB |
05.txt |
RE |
497 ms |
30592 KB |
06.txt |
AC |
1796 ms |
31616 KB |
07.txt |
AC |
213 ms |
31148 KB |
08.txt |
AC |
1471 ms |
30592 KB |
09.txt |
AC |
240 ms |
30096 KB |
10.txt |
RE |
536 ms |
28544 KB |
11.txt |
AC |
179 ms |
28336 KB |
12.txt |
AC |
973 ms |
27776 KB |
13.txt |
AC |
445 ms |
26788 KB |
14.txt |
AC |
876 ms |
25856 KB |
15.txt |
RE |
528 ms |
25216 KB |
16.txt |
AC |
608 ms |
25984 KB |
17.txt |
AC |
269 ms |
37672 KB |
18.txt |
TLE |
2527 ms |
37120 KB |
19.txt |
AC |
228 ms |
33040 KB |
20.txt |
RE |
487 ms |
31488 KB |
21.txt |
AC |
313 ms |
27560 KB |
22.txt |
AC |
933 ms |
27008 KB |
s1.txt |
AC |
3 ms |
8448 KB |
s2.txt |
AC |
3 ms |
8448 KB |