lightoj1325

maksyuki 发表于 oj 分类，标签: 数论-离散对数

27 8月 2015

1325 - Distributing Chocolates

InputNow as the result can be large, I asked for the result modulo 100 000 007 (a prime). But after that I found that this problem is easier than I thought. So, I changed the problem a little bit. I will give you the number of my cousins K and the result modulo 100 000 007. Your task is to find the number of chocolates I have bought. If there are several solutions, you have to find the minimum one.I have bought n chocolates for my young cousins. Every chocolate is different. So, in the contest I added the problem that how many ways I can distribute the chocolates to my K cousins. I can give more chocolates to some cousins, and may give no chocolate to some. For example, I have three cousins and I bought 2 chocolates a and b. Then I can distribute them in the following 9 ways:

Input starts with an integer T (≤ 1000), denoting the number of test cases.

Each case starts with a line containing two integers K (2 ≤ K ≤ 10⁷) and result (0 ≤ result < 100000007). You can assume that the input data is valid, that means a solution exists.

Output

For each case, print the case number and the minimum possible number of chocolates I have bought.

Sample Input	Output for Sample Input
23 92 100	Case 1: 2Case 2: 23502611

题目类型：离散对数

算法分析：直接使用BSGS算法求解即可

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 100000 + 66;

struct hashtable
{
    long long key[maxn];
    long long value[maxn];

    void Init()
    {
        for (long long i = 0; i < maxn; i++)
        {
            key[i] = -1, value[i] = -1;
        }
    }

    void Insert (long long k, long long v)
    {
        long long kk = k % maxn;

        while (key[kk] != -1 && key[kk] != k)
            kk = (kk + 1) % maxn;

        key[kk] = k,value[kk] = v;
    }

    long long Find (long long k)
    {
        long long kk = k % maxn;

        while (key[kk] != -1 && key[kk] != k)
            kk = (kk + 1) % maxn;

        return value[kk];
    }
}Hash;


long long baby_giant (long long x, long long k, long long z)
{
    x %= z,k %= z;
    long long m = (long long) ceil (sqrt (1.0 * z)), pre = 1;

    Hash.Init();Hash.Insert (k, 0);

    for (long long i = 1; i <= m; i++)
    {
        pre = (1ll * pre * x) % z;
        Hash.Insert ((1ll * pre * k) % z, i);
    }

    for (long long i = 0,xm = pre, y = 1; i * m <= z; i++)
    {
        long long j = Hash.Find (y);

        if (j >= 0 && i * m - j >= 0)
            return i * m - j;

        y = (1ll * y * xm) % z;
    }

return -1;
}

int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    int t, flag = 1;
    scanf ("%d", &t);

    long long A, B, C = 100000007;

    while (t--)
    {
        printf ("Case %d: ", flag++);
        scanf ("%lld%lld", &A, &B);
        long long ans = baby_giant (A, B, C);

        printf ("%lld\n", ans);
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 100000 + 66;

struct hashtable

{

long long key[maxn];

long long value[maxn];

void Init()

{

for (long long i = 0; i < maxn; i++)

{

key[i] = -1, value[i] = -1;

}

void Insert (long long k, long long v)

{

long long kk = k % maxn;

while (key[kk] != -1 && key[kk] != k)

kk = (kk + 1) % maxn;

key[kk] = k,value[kk] = v;

}

long long Find (long long k)

{

long long kk = k % maxn;

while (key[kk] != -1 && key[kk] != k)

kk = (kk + 1) % maxn;

return value[kk];

}

}Hash;

long long baby_giant (long long x, long long k, long long z)

{

x %= z,k %= z;

long long m = (long long) ceil (sqrt (1.0 * z)), pre = 1;

Hash.Init();Hash.Insert (k, 0);

for (long long i = 1; i <= m; i++)

{

pre = (1ll * pre * x) % z;

Hash.Insert ((1ll * pre * k) % z, i);

}

for (long long i = 0,xm = pre, y = 1; i * m <= z; i++)

{

long long j = Hash.Find (y);

if (j >= 0 && i * m - j >= 0)

return i * m - j;

y = (1ll * y * xm) % z;

}

return -1;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

int t, flag = 1;

scanf ("%d", &t);

long long A, B, C = 100000007;

while (t--)

{

printf ("Case %d: ", flag++);

scanf ("%lld%lld", &A, &B);

long long ans = baby_giant (A, B, C);

printf ("%lld\n", ans);

}

return 0;

}

lightoj1319

lightoj1337

超客的水墨烟雨

lightoj1325

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30