Regionals 2011,Asia-Phuket D題Twin Apparent Primes!!時計を打つ
8229 ワード
nとtを与えて、1つのnビットの数pを求めて、pとp+2がすべて2からtのすべての整数を除去することができません
3500<=n<=5000,t<=8000
hustからいろいろな人が間違ったコードでこの問題を通過したのを見て、私はとても理解していません.
この問題の具体的な証明はまだ知らない.私は数論が弱いからだ.
でも時計を打つ方法で水を流すことができます.
tは最大8000であり、1つの数がt=8000を満たす場合、8000未満のすべての場合を満たすため、tを観察する.
t=8000時のすべての状況だけを打ち出してもいいです.
1つのnビット数に対して、最小の数は1000であるべきです.0000という数
では、この位置から奇数を列挙し、mod 2~8000の数がテーマの要件を満たしているかどうかを数ごとに見る.
満足できれば、列挙した結果をメモします.もちろん、前の1と0の山は記録しなくてもいいです.
n=3500の場合,プログラム検証により200ビット以上に列挙された.
そこでnごとに100から...00000列挙を開始してもステップ数はあまり列挙されません
そしてnごとにt=8000の下の表を出して、一目見て、せいぜい1000歩以上列挙したかもしれません.
そしてACコード
n個1を直接出力したり、100を出力したりする人が何人かいます.00001の100……0007とか、過ぎていて驚きました
3500<=n<=5000,t<=8000
hustからいろいろな人が間違ったコードでこの問題を通過したのを見て、私はとても理解していません.
この問題の具体的な証明はまだ知らない.私は数論が弱いからだ.
でも時計を打つ方法で水を流すことができます.
tは最大8000であり、1つの数がt=8000を満たす場合、8000未満のすべての場合を満たすため、tを観察する.
t=8000時のすべての状況だけを打ち出してもいいです.
1つのnビット数に対して、最小の数は1000であるべきです.0000という数
では、この位置から奇数を列挙し、mod 2~8000の数がテーマの要件を満たしているかどうかを数ごとに見る.
満足できれば、列挙した結果をメモします.もちろん、前の1と0の山は記録しなくてもいいです.
n=3500の場合,プログラム検証により200ビット以上に列挙された.
そこでnごとに100から...00000列挙を開始してもステップ数はあまり列挙されません
そしてnごとにt=8000の下の表を出して、一目見て、せいぜい1000歩以上列挙したかもしれません.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#define INF 1000007
#define pi acos(-1.0)
#define eps 1.0e-8
using namespace std;
int b[8888];
int n, m;
bool tag[8001];
int p[8001];
int cnt;
void get_prime() // 5000000
{
cnt = 0;
tag[1] = 1;
for (int i = 2; i < 8001; i++)
{
if (!tag[i])
p[cnt++] = i;
for (int j = 0; j < cnt && p[j] * i < 8001; j++)
{
tag[i*p[j]] = 1;
if (i % p[j] == 0)
break;
}
}
}
int main()
{
get_prime();
freopen("C:/Users/Administrator/Desktop/data/ceshi.txt", "w", stdout);
for(n = 3500; n <= 5000; n++)
{
m = 8000;
for(int i = 0; p[i] <= m && i < cnt; i++)
{
int temp = 1;
for(int j = 1; j < n; j++)
temp = temp * 10 % p[i];
b[i] = (temp + 1) % p[i];
}
int pos = 0;
while(1)
{
int flag = 1;
for(int i = 0; p[i] <= m && i < cnt; i++)
{
if(b[i] == 0 || (b[i] + 2) % p[i] == 0)
{
flag = 0;
break;
}
}
if(flag)
{
pos++;
printf("%d,", pos);
break;
}
else
{
pos += 2;
for(int i = 0; p[i] <= m && i < cnt; i++) b[i] = (b[i] + 2) % p[i];
}
}
}
return 0;
}
そしてACコード
n個1を直接出力したり、100を出力したりする人が何人かいます.00001の100……0007とか、過ぎていて驚きました
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#define INF 1000007
#define pi acos(-1.0)
#define eps 1.0e-8
using namespace std;
int a[] = {217,169,7,37,391,607,97,49,19,37,31,667,91,97,37,61,169,229,271,907,7,7,187,91,97,211,19,79,211,61,97,169,697,37,97,799,337,7,247,97,349,169,97,37,217,121,151,7,49,127,19,97,19,37,169,7,187,7,151,7,169,247,217,289,127,7,31,37,31,331,391,7,49,259,61,79,127,157,7,127,7,7,97,577,259,37,487,271,481,499,31,559,121,79,211,121,127,37,7,97,517,157,511,7,19,271,151,169,649,7,7,121,349,37,127,169,19,7,271,61,49,361,361,181,169,211,19,427,49,289,577,187,91,7,229,79,151,211,511,37,409,331,547,199,91,49,49,187,31,211,169,169,61,61,19,79,91,181,319,7,169,271,7,79,31,277,337,7,97,127,301,7,151,31,31,211,187,271,97,169,7,1,19,97,151,37,259,697,7,61,31,211,187,7,49,61,271,187,589,7,451,37,547,451,409,97,289,499,127,229,49,49,1087,61,31,61,349,91,319,37,391,229,271,7,499,67,151,199,409,1327,247,271,517,37,7,37,7,97,31,61,49,1351,37,37,349,61,169,127,427,139,361,157,217,127,49,61,127,7,181,259,7,61,19,31,1279,211,31,79,391,37,139,127,19,79,151,91,187,37,19,7,31,397,379,697,31,79,31,169,91,37,7,121,151,37,97,139,19,67,19,61,229,91,19,79,169,61,49,421,19,7,349,7,49,259,61,37,229,157,31,289,49,61,367,31,127,91,31,79,19,7,31,7,499,7,97,31,61,127,427,61,151,7,349,1147,19,7,151,61,181,247,607,61,127,79,169,91,19,37,31,7,31,127,19,271,277,79,217,7,7,331,97,31,187,49,31,7,151,157,49,37,217,91,19,121,127,37,151,427,151,61,49,91,451,301,211,157,31,37,247,139,169,289,187,259,91,37,337,7,19,169,541,61,271,421,31,91,91,79,337,37,31,211,37,961,151,787,169,49,247,37,181,169,49,91,217,79,169,37,31,49,31,7,151,79,127,361,289,7,151,301,169,259,217,7,151,397,19,97,481,7,229,211,97,361,91,7,19,121,91,91,361,277,187,157,7,7,217,79,391,7,19,91,49,601,421,7,31,127,31,121,97,7,91,211,289,61,361,61,31,97,31,121,97,229,259,49,7,37,211,91,97,139,61,181,577,121,31,391,37,61,367,229,7,181,31,61,169,7,7,127,7,67,151,7,97,49,31,187,97,37,217,7,289,277,19,79,49,127,7,79,271,397,379,7,37,181,151,187,217,127,247,61,127,37,127,37,217,1189,31,577,409,169,511,739,97,211,49,7,19,121,349,37,169,7,61,37,19,169,181,49,49,61,517,7,181,49,19,7,409,169,451,289,289,61,31,121,421,97,61,67,31,91,91,127,49,7,31,7,7,7,19,139,181,91,91,799,187,37,97,61,337,169,7,271,277,79,187,211,121,259,211,7,61,97,151,7,151,61,7,91,61,97,169,37,427,97,19,511,31,541,607,319,37,7,19,37,169,541,247,121,811,7,271,49,7,37,229,247,181,49,49,139,169,31,7,391,187,97,277,61,169,139,271,97,229,79,19,37,301,79,181,37,169,127,319,139,31,169,7,331,247,499,19,91,49,181,151,7,31,7,7,7,61,37,211,7,49,7,7,61,361,169,169,127,217,67,169,247,49,127,319,91,19,199,49,427,151,139,19,499,31,7,37,37,19,61,19,37,49,7,349,7,7,259,31,7,31,157,91,127,451,97,697,61,139,7,19,271,97,451,31,127,301,79,349,7,169,97,289,37,97,397,91,49,361,277,127,37,31,541,151,37,127,121,61,181,37,91,97,7,7,259,7,79,277,91,169,7,7,277,181,469,217,91,19,37,151,7,337,421,19,121,127,229,97,37,19,139,97,7,49,361,217,7,31,31,349,139,289,79,97,229,7,361,37,277,151,211,49,37,277,61,391,31,229,79,709,79,1117,379,187,127,121,529,31,211,19,97,427,121,229,31,139,37,61,121,151,61,31,127,61,7,349,121,49,91,151,97,127,169,337,7,247,97,31,169,31,361,217,37,97,31,169,289,19,61,31,37,49,259,7,7,211,79,259,37,319,271,19,7,271,361,541,331,151,211,91,37,7,61,31,631,181,127,691,61,181,331,19,1,229,301,19,7,7,169,31,7,277,577,49,127,289,271,151,211,229,127,481,37,97,301,7,709,277,79,127,37,49,361,361,259,97,7,127,139,709,37,127,79,49,169,187,79,97,397,451,319,607,61,271,91,187,211,619,97,391,7,19,49,61,61,169,331,97,91,91,7,271,31,271,427,37,91,349,79,7,49,19,7,31,469,97,127,7,7,187,79,49,331,19,559,97,229,169,139,187,499,31,229,19,247,7,61,31,271,19,91,49,91,169,37,409,79,7,271,31,61,127,337,37,97,151,331,181,49,187,121,19,229,169,7,499,301,337,37,7,337,61,181,349,157,61,49,289,319,277,427,31,259,187,607,97,499,169,37,19,97,817,397,49,7,49,7,97,31,217,7,217,61,181,187,7,37,289,79,811,157,31,49,427,457,19,91,7,139,7,37,151,121,91,361,121,727,19,397,301,181,361,7,391,7,271,79,61,277,187,7,19,127,19,97,19,7,259,757,31,97,409,7,19,169,19,79,151,61,31,211,1069,61,517,7,97,361,151,511,151,37,127,127,301,271,127,271,379,49,19,181,97,499,271,127,187,61,151,61,169,517,19,139,409,157,7,247,121,499,229,61,511,49,31,37,559,31,7,139,289,79,19,61,169,211,61,79,391,91,19,97,487,97,151,427,7,37,319,667,31,61,127,247,271,61,127,121,181,49,19,67,409,577,451,259,247,61,169,7,7,97,7,7,181,397,217,97,19,61,127,79,31,127,49,7,97,271,421,259,187,649,19,211,139,7,217,97,169,31,19,331,247,97,31,157,217,517,877,7,211,61,127,757,301,187,151,37,49,79,217,7,31,619,49,49,37,271,151,331,19,91,61,289,181,271,7,49,289,61,127,7,97,391,19,7,19,157,421,391,31,37,31,451,31,91,7,271,391,121,91,427,7,7,349,91,559,331,61,37,367,169,481,37,61,7,19,61,607,259,91,7,151,169,217,7,289,649,97,31,481,139,481,37,97,301,169,91,121,79,31,7,49,97,19,67,151,79,127,37,49,1111,1237,37,7,289,7,511,811,79,61,247,511,61,271,7,217,127,481,79,127,157,301,37,301,331,577,7,31,169,19,7,19,31,187,127,19,139,151,61,49,97,7,391,211,157,847,211,49,7,151,397,127,37,19,391,97,61,127,37,151,7,19,247,19,361,427,79,277,91,229,7,451,277,97,7,97,181,217,97,211,61,19,391,37,67,181,37,31,259,19,37,337,301,337};
int main()
{
int n, m;
while(scanf("%d%d", &n, &m) != EOF)
{
if(!n && !m) break;
int tx = a[n - 3500];
int k = 0;
while(tx)
{
k++;
tx /= 10;
}
putchar('1');
for(int i = 1; i <= n - k - 1; i++) putchar('0');
printf("%d
", a[n - 3500]);
}
return 0;
}