QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#94550#5866. Perfect Harmonyeyiigjkn0 731ms124700kbC++141.5kb2023-04-06 17:17:572023-04-06 17:18:01

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:18:01]
  • 评测
  • 测评结果:0
  • 用时:731ms
  • 内存:124700kb
  • [2023-04-06 17:17:57]
  • 提交

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,le);
		}
		if(ans<=R) printf("Case #%d: %lld\n",_,ans);
		else printf("Case #%d: NO\n",_);
		memset(ri+1,0,sizeof(ll)*n);
	}
}

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 635ms
memory: 124700kb

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: 1666
Case #6: NO
Case #7: NO
Case #8: NO
Case #9: NO
Case #10: 5000
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
Case...

result:

wrong answer 5th lines differ - expected: 'Case #5: 9996', found: 'Case #5: 1666'

Subtask #2:

score: 0
Wrong Answer

Test #2:

score: 0
Wrong Answer
time: 731ms
memory: 124256kb

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: 5000000000000000
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:

wrong answer 3rd lines differ - expected: 'Case #3: 10000000000000000', found: 'Case #3: 5000000000000000'