Submission #3708395
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 400
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[1600005],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<=1600000;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 |
1100 |
Code Size |
1484 Byte |
Status |
AC |
Exec Time |
2314 ms |
Memory |
35532 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 |
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 |
243 ms |
27848 KB |
02.txt |
AC |
1217 ms |
26368 KB |
03.txt |
AC |
242 ms |
26184 KB |
04.txt |
AC |
976 ms |
24832 KB |
05.txt |
AC |
230 ms |
29896 KB |
06.txt |
AC |
1650 ms |
28416 KB |
07.txt |
AC |
206 ms |
29000 KB |
08.txt |
AC |
1339 ms |
27520 KB |
09.txt |
AC |
233 ms |
27844 KB |
10.txt |
AC |
1200 ms |
26368 KB |
11.txt |
AC |
173 ms |
26192 KB |
12.txt |
AC |
898 ms |
24704 KB |
13.txt |
AC |
438 ms |
24644 KB |
14.txt |
AC |
831 ms |
22784 KB |
15.txt |
AC |
158 ms |
24652 KB |
16.txt |
AC |
553 ms |
22784 KB |
17.txt |
AC |
260 ms |
35532 KB |
18.txt |
AC |
2314 ms |
34048 KB |
19.txt |
AC |
222 ms |
30792 KB |
20.txt |
AC |
1613 ms |
29440 KB |
21.txt |
AC |
306 ms |
25420 KB |
22.txt |
AC |
864 ms |
23936 KB |
s1.txt |
AC |
45 ms |
18944 KB |
s2.txt |
AC |
43 ms |
18944 KB |