QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #722547 | #9612. 月亮的背面是粉红色的 | TheZone | 100 ✓ | 2157ms | 420052kb | C++20 | 4.9kb | 2024-11-07 19:29:43 | 2024-11-07 19:29:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
constexpr int p=1e9+7,N=1e8;
constexpr long long lim=9e18-1ll*p*p;
void red(long long&v){if(v>lim||v<-lim)v%=p;}
int mu[N+1];
bitset<N+10>ck;
int pe[3400];
void init(int N)
{
mu[1]=1;
int sum=0;
for(int x=2;x<=N;x++)
{
if(!ck[x])pe[++sum]=x,mu[x]=-1;
while(sum>0&&1ll*x*pe[sum]>N)sum--;
for(int j=1;1ll*x*pe[j]<=N;j++)
{
ck.set(x*pe[j]);
if(x%pe[j]==0)break;
mu[x*pe[j]]=-mu[x];
}
}
}
void calc12(long long&v1,long long &v2,long long n)
{
v1=v2=0;
for(int x=1;1ll*x*x<=n;x++)
v1+=n/x,red(v2+=x*(n/x)%p*((n/x+1)%p));
v1=v1*2;
int s=sqrt(n);
v1=(v1-1ll*s*s)%p;
int vv=1ll*s*(s+1)/2%p;
vv=1ll*vv*vv%p;
v2=v2%p-vv;
}
namespace divcnt1
{
const int N=1000005;
typedef long long ll;
struct qwq {
ll x, y;
qwq (ll x0 = 0, ll y0 = 0) : x(x0), y(y0) {}
inline qwq operator + (const qwq &B) const {return qwq(x + B.x, y + B.y);}
};
ll n;
int top;
qwq stk[N];
inline void push(qwq x) { stk[++top]=x;}
inline bool check(ll x, ll y) {return n < x * y;}
inline bool judge(ll x, qwq v) {return (__int128)n * v.x <= (__int128)x * x * v.y;}
long long S1() {
int i, crn = cbrt(n);
ll srn = sqrt(n), x = n / srn, y = srn + 1;
long long ret = 0;
qwq L, R, M;
push(qwq(1, 0)); push(qwq(1, 1));
while(true) {
for (L = stk[top--]; check(x + L.x, y - L.y); x += L.x, y -= L.y)
ret += x * L.y + (L.y + 1) * (L.x - 1) / 2;
if (y <= crn) break;
for (R = stk[top]; !check(x + R.x, y - R.y); R = stk[--top]) L = R;
for (; M = L + R, 1; )
if (check(x + M.x, y - M.y)) push(R = M);
else {
if (judge(x + M.x, R)) break;
L = M;
}
}
for (i = 1; i < y; ++i) ret += n / i;
return ret*2-srn*srn;
}
}
void calc1(long long&v1,long long n)
{
divcnt1::n=n;
v1=divcnt1::S1()%p;
}
main()
{
cin.tie(0)->sync_with_stdio(0);
long long n;
int m;
cin>>n>>m;
init(__builtin_sqrtl(n));
if(!m)
{
long long ans=0,v1=0;
long long lst=0;
for(int x=1;1ll*x*x<=n;x++)
if(mu[x])
{
if(n/(1ll*x*x)!=lst)
{
lst=n/(1ll*x*x);
calc1(v1,lst);
}
red(ans+=mu[x]*v1);
}
ans%=p;
ans=1ll*ans*ans%p;
cout<<(ans+p)%p;
return 0;
}
long long ans=0,ans2=0,v1=0,v2=0;
long long lst=0;
for(int x=1;1ll*x*x<=n;x++)
if(mu[x])
{
if(n/(1ll*x*x)!=lst)
{
lst=n/(1ll*x*x);
calc12(v1,v2,lst);
}
//cout<<lst<<','<<v1<<','<<v2<<endl;
red(ans+=mu[x]*v1);
red(ans2+=1ll*mu[x]*x*x%p*v2);
}
ans%=p;
ans2%=p;
ans=1ll*ans*ans%p;
ans2=1ll*ans2*ans2%p;
cout<<(ans+p)%p;
if(m)cout<<' '<<(ans2+p)%p<<endl;
}
/*#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
constexpr int p=1e9+7,N=1e8;
constexpr long long lim=9e18-1ll*p*p;
void red(long long&v){if(v>lim||v<-lim)v%=p;}
int mu[N+1];
bitset<N+10>ck;
int pe[3400];
void init(int N)
{
mu[1]=1;
int sum=0;
for(int x=2;x<=N;x++)
{
if(!ck[x])pe[++sum]=x,mu[x]=-1;
while(sum>0&&1ll*x*pe[sum]>N)sum--;
for(int j=1;1ll*x*pe[j]<=N;j++)
{
ck.set(x*pe[j]);
if(x%pe[j]==0)break;
mu[x*pe[j]]=-mu[x];
}
}
}
void calc12(long long&v1,long long &v2,long long n)
{
v1=v2=0;
for(int x=1;1ll*x*x<=n;x++)
v1+=n/x,red(v2+=x*(n/x)%p*((n/x+1)%p));
v1=v1*2;
int s=sqrt(n);
v1=(v1-1ll*s*s)%p;
int vv=1ll*s*(s+1)/2%p;
vv=1ll*vv*vv%p;
v2=v2%p-vv;
}
namespace divcnt1
{
const int N=1000005;
typedef long long ll;
struct qwq {
ll x, y;
qwq (ll x0 = 0, ll y0 = 0) : x(x0), y(y0) {}
inline qwq operator + (const qwq &B) const {return qwq(x + B.x, y + B.y);}
};
ll n;
int top;
qwq stk[N];
inline void push(qwq x) { stk[++top]=x;}
inline bool check(ll x, ll y) {return n < x * y;}
inline bool judge(ll x, qwq v) {return (__int128)n * v.x <= (__int128)x * x * v.y;}
long long S1() {
int i, crn = cbrt(n);
ll srn = sqrt(n), x = n / srn, y = srn + 1;
long long ret = 0;
qwq L, R, M;
push(qwq(1, 0)); push(qwq(1, 1));
while(true) {
for (L = stk[top--]; check(x + L.x, y - L.y); x += L.x, y -= L.y)
ret += x * L.y + (L.y + 1) * (L.x - 1) / 2;
if (y <= crn) break;
for (R = stk[top]; !check(x + R.x, y - R.y); R = stk[--top]) L = R;
for (; M = L + R, 1; )
if (check(x + M.x, y - M.y)) push(R = M);
else {
if (judge(x + M.x, R)) break;
L = M;
}
}
for (i = 1; i < y; ++i) ret += n / i;
return ret*2-srn*srn;
}
}
void calc1(long long&v1,long long n)
{
divcnt1::n=n;
v1=divcnt1::S1()%p;
}
main()
{
cin.tie(0)->sync_with_stdio(0);
long long n;
int m;
cin>>n>>m;
init(__builtin_sqrtl(n));
if(!m)
{
long long ans=0,v1=0;
long long lst=0;
for(int x=1;1ll*x*x<=n;x++)
if(mu[x])
{
if(n/(1ll*x*x)!=lst)
{
lst=n/(1ll*x*x);
calc1(v1,lst);
}
red(ans+=mu[x]*v1);
}
ans=1ll*ans*ans%p;
ans2=1ll*ans2*ans2%p;
cout<<(ans+p)%p;
if(m)cout<<' '<<(ans2+p)%p<<endl;
}*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 3
Accepted
Test #1:
score: 3
Accepted
time: 0ms
memory: 21776kb
input:
1726 1
output:
84290761 74619067
result:
ok 2 number(s): "84290761 74619067"
Test #2:
score: 3
Accepted
time: 0ms
memory: 22036kb
input:
3608 1
output:
433014481 672891299
result:
ok 2 number(s): "433014481 672891299"
Test #3:
score: 3
Accepted
time: 0ms
memory: 22792kb
input:
2921 1
output:
271096225 547734266
result:
ok 2 number(s): "271096225 547734266"
Subtask #2:
score: 3
Accepted
Test #4:
score: 3
Accepted
time: 0ms
memory: 23136kb
input:
6116899 1
output:
219318963 301450440
result:
ok 2 number(s): "219318963 301450440"
Test #5:
score: 3
Accepted
time: 4ms
memory: 21792kb
input:
6260707 1
output:
148720176 263856753
result:
ok 2 number(s): "148720176 263856753"
Test #6:
score: 3
Accepted
time: 0ms
memory: 22860kb
input:
6763677 1
output:
944542490 136397156
result:
ok 2 number(s): "944542490 136397156"
Subtask #3:
score: 8
Accepted
Test #7:
score: 8
Accepted
time: 5ms
memory: 22480kb
input:
6469467712 0
output:
147393348
result:
ok 1 number(s): "147393348"
Test #8:
score: 8
Accepted
time: 5ms
memory: 23276kb
input:
8967004453 0
output:
229436583
result:
ok 1 number(s): "229436583"
Test #9:
score: 8
Accepted
time: 0ms
memory: 23604kb
input:
6636594384 0
output:
995965072
result:
ok 1 number(s): "995965072"
Subtask #4:
score: 8
Accepted
Test #10:
score: 8
Accepted
time: 3ms
memory: 23604kb
input:
8292948816 1
output:
566765721 287485757
result:
ok 2 number(s): "566765721 287485757"
Test #11:
score: 8
Accepted
time: 0ms
memory: 22700kb
input:
8592748771 1
output:
649470692 164561252
result:
ok 2 number(s): "649470692 164561252"
Test #12:
score: 8
Accepted
time: 3ms
memory: 22164kb
input:
9827380808 1
output:
291159931 188690805
result:
ok 2 number(s): "291159931 188690805"
Subtask #5:
score: 8
Accepted
Test #13:
score: 8
Accepted
time: 26ms
memory: 26344kb
input:
900472451132 1
output:
247050500 963765719
result:
ok 2 number(s): "247050500 963765719"
Test #14:
score: 8
Accepted
time: 29ms
memory: 26584kb
input:
850862494659 1
output:
200210720 915108650
result:
ok 2 number(s): "200210720 915108650"
Test #15:
score: 8
Accepted
time: 29ms
memory: 26456kb
input:
851346512859 1
output:
895785763 504512885
result:
ok 2 number(s): "895785763 504512885"
Subtask #6:
score: 10
Accepted
Test #16:
score: 10
Accepted
time: 102ms
memory: 35516kb
input:
9864907300784 1
output:
359943536 720268421
result:
ok 2 number(s): "359943536 720268421"
Test #17:
score: 10
Accepted
time: 91ms
memory: 33232kb
input:
8181674676063 1
output:
839993102 994056029
result:
ok 2 number(s): "839993102 994056029"
Test #18:
score: 10
Accepted
time: 98ms
memory: 35200kb
input:
9893510217522 1
output:
157499971 930653488
result:
ok 2 number(s): "157499971 930653488"
Subtask #7:
score: 13
Accepted
Test #19:
score: 13
Accepted
time: 214ms
memory: 60028kb
input:
96735749745529 0
output:
223354886
result:
ok 1 number(s): "223354886"
Test #20:
score: 13
Accepted
time: 222ms
memory: 62476kb
input:
95243570720799 0
output:
555372474
result:
ok 1 number(s): "555372474"
Test #21:
score: 13
Accepted
time: 247ms
memory: 62832kb
input:
97668723090105 0
output:
84562124
result:
ok 1 number(s): "84562124"
Subtask #8:
score: 14
Accepted
Test #22:
score: 14
Accepted
time: 340ms
memory: 63100kb
input:
94060593399194 1
output:
52991150 887133157
result:
ok 2 number(s): "52991150 887133157"
Test #23:
score: 14
Accepted
time: 351ms
memory: 62396kb
input:
98527940728119 1
output:
281611635 910356955
result:
ok 2 number(s): "281611635 910356955"
Test #24:
score: 14
Accepted
time: 335ms
memory: 59912kb
input:
90501814019947 1
output:
666385143 229785369
result:
ok 2 number(s): "666385143 229785369"
Subtask #9:
score: 16
Accepted
Test #25:
score: 16
Accepted
time: 2157ms
memory: 417800kb
input:
9772457586483846 0
output:
631039552
result:
ok 1 number(s): "631039552"
Test #26:
score: 16
Accepted
time: 2148ms
memory: 420052kb
input:
9889806164705403 0
output:
169322134
result:
ok 1 number(s): "169322134"
Test #27:
score: 16
Accepted
time: 2085ms
memory: 410700kb
input:
9422498258316766 0
output:
413943782
result:
ok 1 number(s): "413943782"
Test #28:
score: 16
Accepted
time: 2151ms
memory: 419136kb
input:
9845978636381962 0
output:
857401052
result:
ok 1 number(s): "857401052"
Test #29:
score: 16
Accepted
time: 2122ms
memory: 417456kb
input:
9761171951453691 0
output:
205712009
result:
ok 1 number(s): "205712009"
Test #30:
score: 16
Accepted
time: 2065ms
memory: 406464kb
input:
9224667465673566 0
output:
143979878
result:
ok 1 number(s): "143979878"
Subtask #10:
score: 17
Accepted
Test #31:
score: 17
Accepted
time: 1160ms
memory: 145552kb
input:
949243849085176 1
output:
508465534 771553755
result:
ok 2 number(s): "508465534 771553755"
Test #32:
score: 17
Accepted
time: 1164ms
memory: 144152kb
input:
924225524519163 1
output:
867410272 870831653
result:
ok 2 number(s): "867410272 870831653"
Test #33:
score: 17
Accepted
time: 1177ms
memory: 147484kb
input:
978079151303393 1
output:
235076358 675828942
result:
ok 2 number(s): "235076358 675828942"
Test #34:
score: 17
Accepted
time: 1150ms
memory: 144336kb
input:
929804617107620 1
output:
790604296 73162158
result:
ok 2 number(s): "790604296 73162158"
Test #35:
score: 17
Accepted
time: 1195ms
memory: 148140kb
input:
989806727450552 1
output:
378550840 783149232
result:
ok 2 number(s): "378550840 783149232"