首页 > ACM题库 > HDU-杭电 > HDU 3223-Decrypt Messages[解题报告]HOJ
2014
03-07

HDU 3223-Decrypt Messages[解题报告]HOJ

Decrypt Messages

问题描述 :

In the game BioHazard 4, the president’s daughter has been abducted by some crazy villagers. Leon S. Kennedy, the secret agent of White House, goes to rescue her. He keeps in contact with Hunnigan, the president’s secretary.

But the time in their contact log has been encrypted, using the following method:

Count the number of seconds from 2000.01.01 00:00:00 to that time, assume this number is x. Then calculate xq, modulo it by a prime number p. The remainder a is the encrypted number.

Your task is to help Leon write a program to decrypt the contact log, and tell him all the possible original time.

1. Remember that if the year can be divided evenly by 4 but can’t be divided evenly by 100, or it can be divided evenly by 400, this year is a leap year. The February of a leap year has 29 days, while the February of other years has 28 days.

2. In this problem, if the year modulo 10 is 5 or 8, at the end of this year, there is one “leap second”, i.e., the second after 2005.12.31 23:59:59 is 2005.12.31 23:59:60, and after that second, it’s 2006.01.01 00:00:00.
You may assume that from 2000.01.01 00:00:00 till that time, less than p seconds have passed.

输入:

There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the test cases.

For each test case, a single line of three integers: p, q, and a. (2<p≤1000000007, 1<q≤10, 0≤a<p, p is always a prime.)

输出:

There are multiple test cases.
The first line of the input contains an integer T, meaning the number of the test cases.

For each test case, a single line of three integers: p, q, and a. (2<p≤1000000007, 1<q≤10, 0≤a<p, p is always a prime.)

样例输入:

2
3 2 1
3 2 2

样例输出:

Case #1:
2000.01.01 00:00:01
2000.01.01 00:00:02
Case #2:
Transmission error

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>
#include <algorithm>
#define P 32000
#define LL long long

int pr[P], pn;
bool notp[P];

void sieve()
{
 for (int i = 2; i < P; ++i) {
 if (!notp[i]) pr[pn++] = i;
 for (int j = 0; j < pn && i * pr[j] < P; ++j) {
 notp[i*pr[j]] = 1;
 if (i%pr[j]==0) break;
 }
 }
}

#define MOD 76543
int hs[MOD], head[MOD], next[MOD], id[MOD], top;

void insert(int x, int y)
{
 int k = x%MOD;
 hs[top] = x, id[top] = y, next[top] = head[k], head[k] = top++;
}

int find(int x)
{
 int k = x%MOD;
 for (int i = head[k]; i; i = next[i]) if (hs[i] == x) return id[i];
 return -1;
}

int BSGS(int a, int b, int n)
{
 memset(head, 0, sizeof(head)); top = 1;
 if (b==1) return 0;
 int m = sqrt(n+.0), j; LL x = 1, p = 1;
 for (int i = 0; i < m; ++i, p = p*a%n) insert(p*b%n, i);
 for (LL i = m; ; i += m) {
 if ((j = find(x=x*p%n)) != -1) return i-j;
 if (i > n) break;
 }
 return -1;
}

int powMod(LL b, LL p, int m)
{
 LL a = 1;
 for (; p; p >>= 1, b = b*b%m) if (p&1) a = a*b%m;
 return a;
}

int pf[10], nf[10], fCnt;

void Factor(int n)
{
 int n2 = sqrt(n+.0); fCnt = 0;
 for (int i = 0; pr[i] <= n2 && n > 1; ++i) if (!(n%pr[i])) {
 for (nf[fCnt] = 1, n/=pr[i]; !(n%pr[i]); n/=pr[i], ++nf[fCnt]);
 pf[fCnt++] = pr[i];
 }
 if (n > 1) nf[fCnt] = 1, pf[fCnt++] = n;
}

int PriRoot(int p)
{
 if (p==2) return 1;
 int phi = p - 1, g, i;
 Factor(phi);
 for (g = 2; g < p; ++g) {
 for (i = 0; i < fCnt; ++i)
 if (powMod(g, phi/pf[i], p) == 1) break;
 if (i == fCnt) break;
 }
 return g;
}

LL ext_gcd(LL a, LL b, LL& x, LL& y)
{
 if (!b) {
 x = 1, y = 0;
 return a;
 }
 LL ret = ext_gcd(b, a%b, y, x);
 y -= a/b*x;
 return ret;
}

int rec[20], md[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool leap(int y)
{
 return !(y%400) || (y%100 && !(y%4));
}

int Year(int y)
{
 int ret = 365*24*60*60;
 if (leap(y)) ret += 24*60*60;
 if (y%10==5 || y%10==8) ++ret;
 return ret;
}

int Month(int y, int m)
{
 int ret = md[m-1]*24*60*60;
 if (leap(y) && m==2) ret += 24*60*60;
 if ((y%10==5 || y%10==8) && m==12) ++ret;
 return ret;
}

int Day(int y, int m, int d)
{
 int ret = 24*60*60;
 if ((y%10==5 || y%10==8) && m==12 && d==31) ++ret;
 return ret;
}

void outDate(int x)
{
 int year = 2000, month = 1, day = 1, hour = 0, minute = 0, second = 0;
 while (x >= Year(year)) x -= Year(year++);
 while (x >= Month(year, month)) x -= Month(year, month++);
 while (x >= Day(year, month, day)) x -= Day(year, month, day++);
 while (x >= 60*60) x -= 60*60, ++hour;
 while (x >= 60) x -= 60, ++minute;
 second = x;
 if (hour == 24){
 hour = 23;
 minute = 59;
 second = 60;
 }
 printf("%d.%02d.%02d %02d:%02d:%02d\n", year, month, day, hour, minute, second);
}

void solve(int a, int b, int p)
{
 if (!b) {
 outDate(0);
 return;
 }
 int g = PriRoot(p);
 int x = BSGS(g, b, p);
 LL y, t, d = ext_gcd(a, p-1, y, t);
 y %= (p-1)/d;
 if (y < 0) y += (p-1)/d;
// printf("%d %d %d %d\n", g, x, y, d);
 if (x == -1 || x%d) {
 puts("Transmission error");
 return;
 }
 while (!x && b!=1) puts("AFS"); 
 for (int i = 0; i < d; ++i) {
 LL ty = y*(x/d)+(p-1)/d*i;
 rec[i] = powMod(g, ty, p);
 }
 std::sort(rec, rec + d);
 for (int i = 0; i < d; ++i) outDate(rec[i]);
}

int main()
{
 sieve();
 int T, cas = 0, a, b, c;
 scanf("%d", &T);
 while (T--) {
// srand(time(NULL));
// c = 1000000007;//465455467;//rand() % (pn-1) + 1;
// a = rand() % 8 + 2, b = (LL)rand()*rand()*rand()%c;//
 scanf("%d%d%d", &c, &a, &b);
 printf("Case #%d:\n", ++cas);
 solve(a, b, c);
 }
 return 0;
}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。