結果

問題 No.28 末尾最適化
ユーザー kotatsugamekotatsugame
提出日時 2021-01-10 07:40:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 822 ms / 5,000 ms
コード長 1,107 bytes
コンパイル時間 975 ms
コンパイル使用メモリ 85,148 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-20 13:08:14
合計ジャッジ時間 2,274 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 822 ms
6,816 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:18:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   18 | main()
      | ^~~~

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int Q;
vector<pair<int,int> >fact(int B)
{
	vector<pair<int,int> >ret;
	for(int i=2;i*i<=B;i++)if(B%i==0)
	{
		int c=0;
		while(B%i==0)B/=i,c++;
		ret.push_back(make_pair(i,c));
	}
	if(B>1)ret.push_back(make_pair(B,1));
	return ret;
}
main()
{
	cin>>Q;
	for(;Q--;)
	{
		long x;
		int N,K,B;
		cin>>x>>N>>K>>B;
		vector<pair<int,int> >ps=fact(B);
		vector<vector<int> >A(N+1);
		for(int i=0;i<=N;i++)
		{
			{
				vector<int>now(ps.size());
				long t=x;
				for(int j=0;j<ps.size();j++)
				{
					int p=ps[j].first;
					int c=0;
					while(t%p==0)t/=p,c++;
					now[j]=c;
				}
				A[i]=now;
			}
			x=1+(x*x+x*12345)%100000009;
		}
		int ans=1e9;
		for(int i=0;i<ps.size();i++)
		{
			sort(A.begin(),A.end(),[&i](const vector<int>&a,const vector<int>&b){
				return a[i]<b[i];
			});
			vector<int>cnt(ps.size());
			for(int j=0;j<K;j++)
			{
				for(int k=0;k<ps.size();k++)cnt[k]+=A[j][k];
			}
			int now=1e9;
			for(int j=0;j<ps.size();j++)now=min(now,cnt[j]/ps[j].second);
			ans=min(ans,now);
		}
		cout<<ans<<endl;
	}
}
0