QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#739441#9612. 月亮的背面是粉红色的I_be_wanna100 ✓2232ms420288kbC++145.2kb2024-11-12 21:46:162024-11-12 21:46:17

Judging History

你现在查看的是最新测评结果

  • [2024-11-12 21:46:17]
  • 评测
  • 测评结果：100
  • 用时：2232ms
  • 内存：420288kb
查看
  • [2024-11-12 21:46:16]
  • 提交

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%=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;
}*/
源文件, 语言: C++14

详细

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 0ms
memory: 22832kb

input:

1726 1

output:

84290761 74619067

result:

ok 2 number(s): "84290761 74619067"

Test #2:

score: 3
Accepted
time: 5ms
memory: 22320kb

input:

3608 1

output:

433014481 672891299

result:

ok 2 number(s): "433014481 672891299"

Test #3:

score: 3
Accepted
time: 0ms
memory: 21692kb

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: 22952kb

input:

6116899 1

output:

219318963 301450440

result:

ok 2 number(s): "219318963 301450440"

Test #5:

score: 3
Accepted
time: 5ms
memory: 22320kb

input:

6260707 1

output:

148720176 263856753

result:

ok 2 number(s): "148720176 263856753"

Test #6:

score: 3
Accepted
time: 0ms
memory: 22652kb

input:

6763677 1

output:

944542490 136397156

result:

ok 2 number(s): "944542490 136397156"

Subtask #3:

score: 8
Accepted

Test #7:

score: 8
Accepted
time: 7ms
memory: 23620kb

input:

6469467712 0

output:

147393348

result:

ok 1 number(s): "147393348"

Test #8:

score: 8
Accepted
time: 4ms
memory: 23828kb

input:

8967004453 0

output:

229436583

result:

ok 1 number(s): "229436583"

Test #9:

score: 8
Accepted
time: 3ms
memory: 22216kb

input:

6636594384 0

output:

995965072

result:

ok 1 number(s): "995965072"

Subtask #4:

score: 8
Accepted

Test #10:

score: 8
Accepted
time: 3ms
memory: 23008kb

input:

8292948816 1

output:

566765721 287485757

result:

ok 2 number(s): "566765721 287485757"

Test #11:

score: 8
Accepted
time: 8ms
memory: 21716kb

input:

8592748771 1

output:

649470692 164561252

result:

ok 2 number(s): "649470692 164561252"

Test #12:

score: 8
Accepted
time: 4ms
memory: 22124kb

input:

9827380808 1

output:

291159931 188690805

result:

ok 2 number(s): "291159931 188690805"

Subtask #5:

score: 8
Accepted

Test #13:

score: 8
Accepted
time: 28ms
memory: 25824kb

input:

900472451132 1

output:

247050500 963765719

result:

ok 2 number(s): "247050500 963765719"

Test #14:

score: 8
Accepted
time: 26ms
memory: 27408kb

input:

850862494659 1

output:

200210720 915108650

result:

ok 2 number(s): "200210720 915108650"

Test #15:

score: 8
Accepted
time: 29ms
memory: 25832kb

input:

851346512859 1

output:

895785763 504512885

result:

ok 2 number(s): "895785763 504512885"

Subtask #6:

score: 10
Accepted

Test #16:

score: 10
Accepted
time: 101ms
memory: 35312kb

input:

9864907300784 1

output:

359943536 720268421

result:

ok 2 number(s): "359943536 720268421"

Test #17:

score: 10
Accepted
time: 96ms
memory: 34348kb

input:

8181674676063 1

output:

839993102 994056029

result:

ok 2 number(s): "839993102 994056029"

Test #18:

score: 10
Accepted
time: 106ms
memory: 35864kb

input:

9893510217522 1

output:

157499971 930653488

result:

ok 2 number(s): "157499971 930653488"

Subtask #7:

score: 13
Accepted

Test #19:

score: 13
Accepted
time: 240ms
memory: 63540kb

input:

96735749745529 0

output:

223354886

result:

ok 1 number(s): "223354886"

Test #20:

score: 13
Accepted
time: 246ms
memory: 62492kb

input:

95243570720799 0

output:

555372474

result:

ok 1 number(s): "555372474"

Test #21:

score: 13
Accepted
time: 242ms
memory: 63380kb

input:

97668723090105 0

output:

84562124

result:

ok 1 number(s): "84562124"

Subtask #8:

score: 14
Accepted

Test #22:

score: 14
Accepted
time: 354ms
memory: 62944kb

input:

94060593399194 1

output:

52991150 887133157

result:

ok 2 number(s): "52991150 887133157"

Test #23:

score: 14
Accepted
time: 347ms
memory: 62836kb

input:

98527940728119 1

output:

281611635 910356955

result:

ok 2 number(s): "281611635 910356955"

Test #24:

score: 14
Accepted
time: 346ms
memory: 62360kb

input:

90501814019947 1

output:

666385143 229785369

result:

ok 2 number(s): "666385143 229785369"

Subtask #9:

score: 16
Accepted

Test #25:

score: 16
Accepted
time: 2203ms
memory: 418308kb

input:

9772457586483846 0

output:

631039552

result:

ok 1 number(s): "631039552"

Test #26:

score: 16
Accepted
time: 2195ms
memory: 420168kb

input:

9889806164705403 0

output:

169322134

result:

ok 1 number(s): "169322134"

Test #27:

score: 16
Accepted
time: 2179ms
memory: 411512kb

input:

9422498258316766 0

output:

413943782

result:

ok 1 number(s): "413943782"

Test #28:

score: 16
Accepted
time: 2232ms
memory: 420288kb

input:

9845978636381962 0

output:

857401052

result:

ok 1 number(s): "857401052"

Test #29:

score: 16
Accepted
time: 2185ms
memory: 418756kb

input:

9761171951453691 0

output:

205712009

result:

ok 1 number(s): "205712009"

Test #30:

score: 16
Accepted
time: 2183ms
memory: 408352kb

input:

9224667465673566 0

output:

143979878

result:

ok 1 number(s): "143979878"

Subtask #10:

score: 17
Accepted

Test #31:

score: 17
Accepted
time: 1174ms
memory: 145924kb

input:

949243849085176 1

output:

508465534 771553755

result:

ok 2 number(s): "508465534 771553755"

Test #32:

score: 17
Accepted
time: 1173ms
memory: 143904kb

input:

924225524519163 1

output:

867410272 870831653

result:

ok 2 number(s): "867410272 870831653"

Test #33:

score: 17
Accepted
time: 1202ms
memory: 147656kb

input:

978079151303393 1

output:

235076358 675828942

result:

ok 2 number(s): "235076358 675828942"

Test #34:

score: 17
Accepted
time: 1164ms
memory: 146336kb

input:

929804617107620 1

output:

790604296 73162158

result:

ok 2 number(s): "790604296 73162158"

Test #35:

score: 17
Accepted
time: 1196ms
memory: 149160kb

input:

989806727450552 1

output:

378550840 783149232

result:

ok 2 number(s): "378550840 783149232"
English 繁體中文 简体中文

服务器时间: 2024-12-05 01:37:25 | 开源项目