#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#define ll long long
#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
template <int mod>
struct Modint{
int val;
Modint(int _val=0){val=_val%mod;if(val<0) val+=mod;}
Modint operator +(const Modint& o) const {
Modint res;
res.val=val+o.val;
if(res.val>=mod) res.val-=mod;
return res;
}
Modint operator +(const int& o) const {return Modint(val+o);}
Modint operator -() const {
Modint res;
res.val=-val;
if(res.val<0) res.val+=mod;
return res;
}
Modint operator -(const Modint& o) const {
Modint res;
res.val=val-o.val;
if(res.val<0) res.val+=mod;
return res;
}
Modint operator -(const int& o) const {return Modint(val-o);}
Modint operator *(const Modint& o) const {return Modint(val*o.val);}
Modint operator *(const int& o) const {return Modint(val*(o%mod));}
Modint operator +=(const Modint& o){*this=(*this)+o;return *this;}
Modint operator -=(const Modint& o){*this=(*this)-o;return *this;}
Modint operator *=(const Modint& o){*this=(*this)*o;return *this;}
Modint Pow(int b) const {
Modint tmp(val),ret(1);
while(b){
if(b&1) ret*=tmp;
b>>=1;tmp*=tmp;
}
return ret;
}
Modint Pow(const Modint& a, int b) const {return a.Pow(b);}
inline Modint inv() const {return (*this).Pow(mod-2);}
Modint operator /(const Modint& o) const {return *this*o.inv();}
Modint operator /(const int& o) const {return *this*Modint(o).inv();}
bool operator ==(const Modint& o) const {return val==o.val;}
};
template<int mod>
ostream& operator << (ostream& o, Modint<mod> x){return o << x.val;}
template<int mod>
Modint<mod> operator +(const int& x, const Modint<mod>& y){return Modint<mod>(x+y.val);}
template<int mod>
Modint<mod> operator -(const int& x, const Modint<mod>& y){return Modint<mod>(x-y.val);}
template<int mod>
Modint<mod> operator *(const int& x, const Modint<mod>& y){return Modint<mod>(x%mod*y.val);}
#define modint Modint<MOD>
vector<modint> inv,fac,invfac;
void init_comb(int N){
inv.resize(N),fac.resize(N),invfac.resize(N);
inv[1]=1,fac[0]=1,invfac[0]=1;
rep2(i,2,N) inv[i]=inv[MOD%i]*(MOD-MOD/i);
rep2(i,1,N) fac[i]=fac[i-1]*i;
rep2(i,1,N) invfac[i]=invfac[i-1]*inv[i];
}
inline modint C(int n, int m){return m>n||m<0?modint(0):fac[n]*invfac[m]*invfac[n-m];}
inline modint H(int n, int m){return C(n+m-1,n);}
const int maxn=100005,maxm=5,maxk=7777714;
//i_am_noob
//#define wiwihorz
int n,m,q,mobius[maxn],res;
vector<vector<int>> factors(maxn),pr(maxn);
bool isp[maxn];
int count(int k, int l, int r){
int tot=0;
/*
if((r-l)*sz(pr[k])<=sz(factors[k])){
rep2(i,l,r+1){
bool flag=1;
for(auto p: pr[k]) if(i%p==0) flag=0;
tot+=flag;
}
return tot;
}
*/
if(l==0){
if(k==1) tot++;
l++;
}
for(auto i: factors[k]) tot+=mobius[i]*(r/i-(l-1)/i);
return tot;
}
void solve(int x, int y, int f, int dir){
//0: up, 1: down, 2: left, 3: right
if(dir==0){
res+=count(y,x-f,x-1);
if(f==1) return;
x-=f;
res+=count(abs(x-y),x-f/2,x-1)+count(x+y,x-f/2,x-1);
solve(x-f/2,y-f/2,f/2,0);
solve(x-f/2,y-f/2,f/2,2);
solve(x-f/2,y+f/2,f/2,0);
solve(x-f/2,y+f/2,f/2,3);
}
else if(dir==1){
res+=count(y,x+1,x+f);
if(f==1) return;
x+=f;
res+=count(abs(x-y),x+1,x+f/2)+count(x+y,x+1,x+f/2);
solve(x+f/2,y-f/2,f/2,1);
solve(x+f/2,y-f/2,f/2,2);
solve(x+f/2,y+f/2,f/2,1);
solve(x+f/2,y+f/2,f/2,3);
}
else if(dir==2){
res+=count(x,y-f,y-1);
if(f==1) return;
y-=f;
res+=count(abs(x-y),y-f/2,y-1)+count(x+y,y-f/2,y-1);
solve(x-f/2,y-f/2,f/2,2);
solve(x-f/2,y-f/2,f/2,0);
solve(x+f/2,y-f/2,f/2,2);
solve(x+f/2,y-f/2,f/2,1);
}
else{
res+=count(x,y+1,y+f);
if(f==1) return;
y+=f;
res+=count(abs(x-y),y+1,y+f/2)+count(x+y,y+1,y+f/2);
solve(x-f/2,y+f/2,f/2,3);
solve(x-f/2,y+f/2,f/2,0);
solve(x+f/2,y+f/2,f/2,3);
solve(x+f/2,y+f/2,f/2,1);
}
}
void orzck(){
/*
de[0]=1;
rep2(i,1,11) de[i]=2*pow2(i)+4*de[i-1];
rep(11) bug(i,de[i]);
*/
isp[0]=isp[1]=0;
rep2(i,2,maxn) isp[i]=1;
rep2(i,2,maxn) if(isp[i]) for(int j=i*2; j<maxn; j+=i) isp[j]=0;
mobius[1]=1;
rep2(i,1,maxn) for(int j=i*2; j<maxn; j+=i) mobius[j]-=mobius[i];
rep2(i,1,maxn) if(mobius[i]) for(int j=i; j<maxn; j+=i) factors[j].pb(i);
rep2(i,1,maxn) if(isp[i]) for(int j=i; j<maxn; j+=i) pr[j].pb(i);
rep(10) bug(pr[i]);
cin >> n >> m >> q;
while(q--){
int x,y,f;
cin >> x >> y >> f;
x--,y--;
if(__gcd(x,y)==1) res++;
solve(x,y,f,0);
}
print(res);
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
// #ifdef i_am_noob
// freopen("input1.txt","r",stdin);
// freopen("output1.txt","w",stdout);
// freopen("output2.txt","w",stderr);
// #endif
cout << fixed << setprecision(15);
int t;
#ifdef wiwihorz
cin >> t;
#else
t=1;
#endif
ld start=clock();
while(t--) orzck();
bug((clock()-start)/CLOCKS_PER_SEC);
return 0;
}
Compilation message
squirrel.cpp: In function 'void orzck()':
squirrel.cpp:34:18: warning: statement has no effect [-Wunused-value]
34 | #define bug(...) 777771449
| ^~~~~~~~~
squirrel.cpp:189:13: note: in expansion of macro 'bug'
189 | rep(10) bug(pr[i]);
| ^~~
squirrel.cpp: In function 'int main()':
squirrel.cpp:34:18: warning: statement has no effect [-Wunused-value]
34 | #define bug(...) 777771449
| ^~~~~~~~~
squirrel.cpp:217:5: note: in expansion of macro 'bug'
217 | bug((clock()-start)/CLOCKS_PER_SEC);
| ^~~
squirrel.cpp:215:8: warning: unused variable 'start' [-Wunused-variable]
215 | ld start=clock();
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
18328 KB |
Output is correct |
| 2 |
Incorrect |
169 ms |
18280 KB |
Output isn't correct |
| 3 |
Correct |
2253 ms |
18284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3816 ms |
18280 KB |
Output isn't correct |
| 2 |
Correct |
3679 ms |
18376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4768 ms |
18244 KB |
Time limit exceeded |
| 2 |
Execution timed out |
4787 ms |
18268 KB |
Time limit exceeded |
| 3 |
Execution timed out |
4790 ms |
18244 KB |
Time limit exceeded |
| 4 |
Execution timed out |
4781 ms |
18256 KB |
Time limit exceeded |
| 5 |
Execution timed out |
4749 ms |
18260 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4790 ms |
18276 KB |
Time limit exceeded |
| 2 |
Execution timed out |
4791 ms |
18332 KB |
Time limit exceeded |
| 3 |
Execution timed out |
4793 ms |
18160 KB |
Time limit exceeded |
| 4 |
Execution timed out |
4786 ms |
18248 KB |
Time limit exceeded |
| 5 |
Execution timed out |
4797 ms |
18244 KB |
Time limit exceeded |
| 6 |
Execution timed out |
4784 ms |
18244 KB |
Time limit exceeded |
| 7 |
Execution timed out |
4793 ms |
18188 KB |
Time limit exceeded |
| 8 |
Execution timed out |
4790 ms |
18244 KB |
Time limit exceeded |
| 9 |
Execution timed out |
4783 ms |
18244 KB |
Time limit exceeded |
| 10 |
Execution timed out |
4767 ms |
18392 KB |
Time limit exceeded |
