#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll,ll> Pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define repp(i, n) for(int i=1;i<=n;i++)
#define all(x) x.begin(), x.end()
#define geti1(X) scanf("%d",&X)
#define geti2(X,Y) scanf("%d%d",&X,&Y)
#define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W)
#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__)
#define INF 987654321
#define IINF 987654321987654321
#define MAXV 3000500
#define MOD 1234567
int N,M,T,K;
vector<int> plist[100500];
int p[100500];
int cnt[1000500];
int Bsize;
struct query{
int l,r,n;
};
bool cmp(query& a, query& b){
if( a.l/Bsize == b.l/Bsize ) return a.r < b.r;
else return a.l/Bsize < b.l/Bsize;
}
void init(){
rep(i,100500) plist[i].clear();
memset(cnt,0,sizeof cnt);
}
vector<int> getp(int n){
vector<int> res;
for(int i=1;i*i<=n;i++){
if( n%i == 0 ){
if( i*i == n ) res.pb(i);
else{
res.pb(i);
res.pb(n/i);
}
}
}
return res;
}
void solve(){
init();
geti(N,M);
repp(i,N) geti(p[i]);
repp(j,N){
int n = p[j];
for(int i=1;i*i<=n;i++){
if( n%i == 0 ){
if( i*i == n ) plist[j].pb(i);
else{
plist[j].pb(i);
plist[j].pb(n/i);
}
}
}
}
vector<query> q;
repp(i,M){
int a,b,c; geti(a,b,c);
q.push_back({b,c,a});
}
Bsize = (int) sqrt(1.0*N);
sort(all(q),cmp);
int ans = 0;
int l=1, r=0; int sum = 0;
for(int i=0;i<q.size();i++){
sum = 0;
query& e = q[i];
int ql = e.l, qr = e.r;
while( r < qr ){
r++;
//sum += p[r]*(2*c[p[r]]+1); cnt[p[r]]++;
for(auto x : plist[r]) cnt[x]++;
}
while( r > qr ){
//sum += p[r]*(1-2*c[p[r]]); cnt[p[r]]--;
for(auto x : plist[r]) cnt[x]--;
r--;
}
while( l < ql ){
//sum += p[l]*(1-2*c[p[l]]); cnt[p[l]]--;
for(auto x : plist[l]) cnt[x]--;
l++;
}
while( l > ql ){
l--;
for(auto x : plist[l]) cnt[x]++;
//sum += p[l]*(2*c[p[l]]+1); cnt[p[l]]++;
}
int n = e.n;
for(int x=1;x*x<=n;x++){
if( n%x == 0 ){
if( x*x == n ){
if( cnt[x] == 0 ) sum++;
}
else{
if( cnt[x] == 0 ) sum++;
if( cnt[n/x] == 0 ) sum++;
}
}
}
/*
vector<int> v = getp(n);
for(auto e : v){
if( cnt[e] == 0 ) sum++;
}
*/
ans += sum;
}
printf("%d\n",ans);
}
#include <ctime>
int main(){
clock_t begin = clock();
setbuf(stdout,NULL);
int tc; scanf("%d",&tc);
repp(t,tc){
printf("Case #%d\n",t);
solve();
}
clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
cout << elapsed_secs << endl;
}
Compilation message
city.cpp: In function 'void solve()':
city.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<q.size();i++){
^
city.cpp:83:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
geti(N,M);
^
city.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
repp(i,N) geti(p[i]);
^
city.cpp:101:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int a,b,c; geti(a,b,c);
^
city.cpp: In function 'int main()':
city.cpp:165:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int tc; scanf("%d",&tc);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
8692 KB |
Execution killed because of forbidden syscall clock_gettime (228) |
| 2 |
Halted |
0 ms |
0 KB |
- |
