QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#391969 | #8177. Sum is Integer | i_am_noob# | WA | 0ms | 3752kb | C++14 | 1.5kb | 2024-04-16 22:59:27 | 2024-04-16 22:59:28 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
const int mod=998244353,N=200005;
const ll p=1945555039024054273,q=9223372036737335297;
ll mul(ll x, ll y, ll mod){return __int128(x)*y%mod;}
ll Pow(ll x, ll y, ll mod){ll res=1; for(; y; y>>=1,x=mul(x,x,mod)) if(y&1) res=mul(res,x,mod); return res;}
void ahcorz(){
int n; cin >> n;
vector<pair<ll,ll>> vec(n+1);
vec[0]={0,0};
vector<ll> vec2(n+1);
vec2[0]=0;
for(int i=0; i<n; ++i){
int x,y; cin >> x >> y;
x%=y;
vec[i+1]={(__int128(0)+vec[i].first+mul(x,Pow(y,p-2,p),p))%p,(__int128(0)+vec[i].second+mul(x,Pow(y,q-2,q),q))%q};
vec2[i+1]=vec[i+1].first-vec[i+1].second;
cout << vec[i+1].first << ' ' << vec[i+1].second << "\n";
}
sort(all(vec2));
ll res=0;
for(int i=0; i<sz(vec2); ++i){
res+=upper_bound(all(vec2),vec2[i])-lower_bound(all(vec2),vec2[i]);
}
res-=sz(vec2);
res/=2;
for(int i=0; i<sz(vec2); ++i){
res+=upper_bound(all(vec2),vec2[i]-p)-lower_bound(all(vec2),vec2[i]-p);
res+=upper_bound(all(vec2),vec2[i]+q)-lower_bound(all(vec2),vec2[i]+q);
res+=upper_bound(all(vec2),vec2[i]-p+q)-lower_bound(all(vec2),vec2[i]-p+q);
}
cout << res << "\n";
}
signed main(){
ios_base::sync_with_stdio(0),cin.tie(0);
int t=1;// cin >> t;
while(t--){
ahcorz();
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3752kb
input:
4 1 6 1 3 1 2 1 2
output:
1621295865853378561 1537228672789555883 972777519512027137 4611686018368667649 1 1 972777519512027138 4611686018368667650 2
result:
wrong answer 1st words differ - expected: '2', found: '1621295865853378561'