QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94551#5866. Perfect Harmonyeyiigjkn43 ✓734ms125388kbC++141.6kb2023-04-06 17:21:032023-04-06 17:21:05

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-06 17:21:05]
  • 评测
  • 测评结果:43
  • 用时:734ms
  • 内存:125388kb
  • [2023-04-06 17:21:03]
  • 提交

answer

# include <bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int N=1e8;
constexpr ll INF=1e18;
int prime[10000010],m=0,tot;
ll a[10010],ri[10010],P[20],C[20];
bool npri[100000010];
inline void chkmin(ll &x,const ll &y){x=min(x,y);}
ll dfs(int d,ll cur,ll le)
{
	if(d>tot) return cur>=le?cur:INF;
	ll ans=dfs(d+1,cur,le);
	for(int i=1;i<=C[d];i++) chkmin(ans,dfs(d+1,cur*=P[d],le));
	return ans;
}
ll calc(ll n,ll le)
{
	tot=0;
	for(int i=1;i<=m && prime[i]*prime[i]<=n;i++)
		if(n%prime[i]==0)
		{
			P[++tot]=prime[i];C[tot]=0;
			for(;n%P[tot]==0;n/=P[tot]) C[tot]++;
		}
	if(n>1) P[++tot]=n,C[tot]=1;
	return dfs(1,1,le);
}
int main()
{
	int T,n;
	ll L,R;
	npri[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!npri[i]) prime[++m]=i;
		for(int j=1;j<=m && i*prime[j]<=N;j++)
		{
			npri[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		ll ans=INF;
		scanf("%d%lld%lld",&n,&L,&R);
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
		sort(a+1,a+n+1);
		for(int i=n;i;i--) ri[i]=__gcd(ri[i+1],a[i]);
		ll le=1;
		if(ri[1]>=L) chkmin(ans,calc(ri[1],L));
		for(int i=1;i<=n;i++)
		{
			ll t=__gcd(le,a[i]);
			if(le/t>R/a[i]) break;
			le=le/t*a[i];
			if(i<n)
			{
				if(le>ri[i+1] || ri[i+1]%le || ri[i+1]<L) continue;
				else if(le<L) chkmin(ans,le*calc(ri[i+1]/le,(L+le-1)/le));
				else chkmin(ans,le);
			}
			else chkmin(ans,(L+le-1)/le*le);
		}
		if(ans<=R) printf("Case #%d: %lld\n",_,ans);
		else printf("Case #%d: NO\n",_);
		memset(ri+1,0,sizeof(ll)*n);
	}
	return 0;
}

詳細信息

Subtask #1:

score: 8
Accepted

Test #1:

score: 8
Accepted
time: 639ms
memory: 125388kb

input:

40
3 2 100
3 5 7
4 8 16
1 20 5 2
7 5 10000
9942 9762 9822 9978 9714 9678 9726
4 2 10000
3 17 4 49
10 8331 9997
238 833 34 2 119 98 49 7 17 14
5 3299 8227
4863 6630 5752 498 4148
5 5899 7578
4808 3143 8259 9828 6133
5 3477 3514
2755 1104 6009 8970 3195
5 5795 6372
2431 3458 3070 4892 9336
2 5001 1000...

output:

Case #1: NO
Case #2: 10
Case #3: 6
Case #4: 9996
Case #5: 9996
Case #6: NO
Case #7: NO
Case #8: NO
Case #9: NO
Case #10: 10000
Case #11: NO
Case #12: NO
Case #13: NO
Case #14: 15
Case #15: NO
Case #16: 1
Case #17: 2310
Case #18: 23
Case #19: NO
Case #20: NO
Case #21: NO
Case #22: NO
Case #23: NO
Cas...

result:

ok 40 lines

Subtask #2:

score: 35
Accepted

Test #2:

score: 35
Accepted
time: 734ms
memory: 124180kb

input:

40
3 2 100
3 5 7
4 8 16
1 20 5 2
2 5000000000000001 10000000000000000
2500000000000000 5000000000000000
2888 2 10000000000000000
15661 20393 4889 14929 26053 10529 2897 13009 15361 2707 12619 22153 1453 21739 3709 1151 25033 22157 18919 25733 25579 15643 14029 15101 8447 1381 7669 797 9419 1129 1795...

output:

Case #1: NO
Case #2: 10
Case #3: 10000000000000000
Case #4: NO
Case #5: 9999999999999996
Case #6: 304250263527210
Case #7: NO
Case #8: 223092870
Case #9: 6469693230
Case #10: NO
Case #11: 302977
Case #12: NO
Case #13: 1
Case #14: NO
Case #15: 6064949221531200
Case #16: 4900956
Case #17: NO
Case #18:...

result:

ok 40 lines

Extra Test:

score: 0
Extra Test Passed