QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136702 | #241. Chiaki Sequence Revisited | Delay_for_five_minutes# | 0 | 270ms | 3424kb | C++20 | 713b | 2023-08-09 10:16:22 | 2023-08-09 10:16:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll n;
ll sum(ll x){
ll res=1;
for(int i=60;i>=0;--i){
ll k=x>>i;
k=(k+1)>>1;
res+=k*(i+1);
}
// cout<<x<<' '<<res<<'\n';
return res;
}
ll calc(ll x){
ll res=1;
for(int i=60;i>=0;--i){
ll k=(((x>>i)+1)>>1)%mod;
res+=k*k%mod*((1ll<<i)%mod)%mod*(i+1)%mod;
}
return res;
}
void solve(){
cin>>n;
ll l=1,r=n,mid,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(sum(mid)<=n)l=mid+1,ans=mid;
else r=mid-1;
}
//cout<<ans<<'\n';
cout<<(calc(ans)+(n-sum(ans))%mod*((ans+1)%mod)%mod)%mod;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int T;
cin>>T;
while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 270ms
memory: 3424kb
input:
100000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...
output:
124691317212632384553616977869610611712914115316618019420922524125727328930632434236138140142144246448650953355758160563065668270973776579382285288291394597710091041107311051138117212061241127713131349138614241462150115411581162116611702174417861829187319171961200620522098214521932241228923372385243...
result:
wrong answer 1st lines differ - expected: '1', found: '124691317212632384553616977869...2847743293636961298029366989021'