首页 > ACM题库 > HDU-杭电 > hdu 2421 Deciphering Password-最小生成树-[解题报告]C++
2014
01-26

hdu 2421 Deciphering Password-最小生成树-[解题报告]C++

Deciphering Password

问题描述 :

Xiaoming has just come up with a new way for encryption, by calculating the key from a publicly viewable number in the following way:
Let the public key N = AB, where 1 <= A, B <= 1000000, and a0, a1, a2, …, ak-1 be the factors of N, then the private key M is calculated by summing the cube of number of factors of all ais. For example, if A is 2 and B is 3, then N = AB = 8, a0 = 1, a1 = 2, a2 = 4, a3 = 8, so the value of M is 1 + 8 + 27 + 64 = 100.
However, contrary to what Xiaoming believes, this encryption scheme is extremely vulnerable. Can you write a program to prove it?

输入:

There are multiple test cases in the input file. Each test case starts with two integers A, and B. (1 <= A, B <= 1000000). Input ends with End-of-File.
Note: There are about 50000 test cases in the input file. Please optimize your algorithm to ensure that it can finish within the given time limit.

输出:

There are multiple test cases in the input file. Each test case starts with two integers A, and B. (1 <= A, B <= 1000000). Input ends with End-of-File.
Note: There are about 50000 test cases in the input file. Please optimize your algorithm to ensure that it can finish within the given time limit.

样例输入:

2 2
1 1
4 7

样例输出:

Case 1: 36
Case 2: 1
Case 3: 4393

读不懂题目的孩子伤不起啊~~~~~~~这题我第一次理解为n的所有约数的立方和,打完一看,样例都不对。。。再读读题,以为是求出n的约数个数x,然后求1^3+2^3+3^3+…+x^3,打完了也能过样例,交上去却WA。。。无奈只好翻别人的解题报告看,才明白题目的意思是求g(n)=∑f(d)^3 (d|n,f(n)表示n的约数个数)
易证g(n)为积性函数,即若gcd(n,m)=1则g(nm)=g(n)*g(m)。所以对n分解素因数后N=p1^a1 * p2^a2 ……pj^aj,则可得g(n)=g(p1^a1)*……g(pj^aj)。
而对于每个g(p1^a1)=1^3+……(a1+1)^3=(a1+1)^2*(a1+2)^2 /4。依此思路,不难解出本题。

/*
 * hdu2421/win.cpp
 * Created on: 2012-11-2
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MOD = 10007;
const int _4MOD = 4 * MOD;
typedef long long LL;
typedef vector<pair<int, int> > Int_Pair;
void get_prime_table(int N, vector<int> &pt) {
    vector<bool> ip;
    ip.resize(N + 1);
    fill(ip.begin(), ip.end(), true);
    int i, j, s, t = N - 1;
    for (i = 3; i <= N; i++) {
        s = (int) sqrt(i);
        for (j = 2; j <= s; j++) {
            if (i % j == 0)    break;
        }
        if (j <= s) {            ip[i] = false; t--;        }
    }
    pt.resize(t);
    t = 0;
    for(int i = 2; i <= N; i++) {
        if(ip[i]) {    pt[t++] = i;    }
    }
}
void get_prime_factor(int N, Int_Pair &f, const vector<int> &p) {
    int i, t, n, pl = p.size();
    f.clear();
    for(i = 0; i < pl; i++) {
        t = p[i];
        if(N % t == 0) {
            n = 0;
            while(N % t == 0) {
                n++;    N /= t;
            }
            f.push_back(make_pair(t, n));
        }
        if(N == 1) {    break;    }
    }
    if(N > 1) {
        f.push_back(make_pair(N, 1));
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    vector<int> prime_table;
    get_prime_table(2000, prime_table);
    int A, B, t = 1, n, ans;
    LL temp;
    while(scanf("%d%d", &A, &B) == 2) {
        Int_Pair ip;
        get_prime_factor(A, ip, prime_table);
        ans = 1;
        for(int i = 0, len = ip.size(); i < len; i++) {
            n = (ip[i].second * (LL)B + 1) % _4MOD;
            temp = ((n * n) % _4MOD) * (((n + 1) * (n + 1)) % _4MOD);
            temp = (temp % _4MOD) / 4;
            ans *= temp;
            ans %= MOD;
        }
        printf("Case %d: %d\n", t++, ans);
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/moonbay/archive/2012/11/02/2752031.html


  1. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.