이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 29;
const int K = 1000000;
int a;
int sol[K + 5];
int solLength[K + 5];
int dp0,dp1,sumdp;
void afis(int M)
{
if (solLength[sumdp] == 0 or M < solLength[sumdp])
{
solLength[sumdp] = M;
sol[sumdp] = a;
}
}
void bkt(int pos,int pz,int sumant)
{
if (sumdp > K)
return;
if (pos != 1){
if(solLength[sumdp] != 0 && solLength[sumdp] + 15 < pz){
return;
}
afis(pz - 1);
}
if (pz == N + 1)
return;
else
{
if (pos & 1)
{
if (pos == 1)
{
dp0 = 1;
dp1 = 1;
for (int lung = 1; lung <= N; lung++)
{
a &= ~(1 << (pz + lung - 1));
sumdp = lung;
bkt(pos + 1,lung + 1,lung);
}
}
else
{
dp0 += sumant;
for (int lung = 1; lung <= N - pz + 1; lung++)
{
a &= ~(1 << (pz + lung - 1));
sumdp += dp0 * lung;
bkt(pos + 1,pz + lung,dp0 * lung);
sumdp -= dp0 * lung;
}
dp0 -= sumant;
}
}
else
{
dp1 += sumant;
for (int lung = 1; lung <= N - pz + 1; lung++)
{
a |= 1 << (pz + lung - 1);
sumdp += dp1 * lung;
bkt(pos + 1,pz + lung,dp1 * lung);
sumdp -= dp1 * lung;
}
dp1 -= sumant;
}
}
}
int phi[1000005];
const int NMAX = 1e6 + 2;
void prec_phi()
{
for (int i = 1; i <= NMAX; i++)
phi[i] = i;
for (int i = 2; i <= NMAX; i++)
if (phi[i] == i)
for (int j = i; j <= NMAX; j += i)
phi[j] = (phi[j] / i) * (i - 1);
}
signed main()
{
//for (int i = 1; i <= N; i++)
// found[i] = true;
bkt(1,1,0);
//for (int i = 1; i <= 50; i++)
// cout << sol[i].size() << endl;
//bktsus(1,1,0);
prec_phi();
/*for (int i = 1; i <= K; i++)
if (!found[i])
cout << i << endl;*/
//for (int i = 1; i <= N; i++)
// cout << i << ' ' << cnt[i] << ' ' << cnt2[i] << endl;
int tc;
cin >> tc;
while (tc--)
{
int kk;
cin >> kk;
cout << phi[kk + 2] << '\n';
for (int i = 1; i <= solLength[kk]; i++)
{
if (sol[kk] & (1 << i))
cout << 1 << ' ';
else
cout << 0 << ' ';
}
cout << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |