精华内容
下载资源
问答
  • Discrete Logging Given a prime P, 2 <= P < 2 31, an integer B, 2 <= B < P, and an integer N, 1 &... P, compute the discrete logarithm of N, base B, modulo P....

    Discrete Logging

    Given a prime P, 2 <= P < 2 31, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, base B, modulo P. That is, find an integer L such that
    
        BL == N (mod P)
    

    Input
    Read several lines of input, each containing P,B,N separated by a space.
    Output
    For each line print the logarithm on a separate line. If there are several, print the smallest; if there is none, print “no solution”.
    Sample Input

    5 2 1
    5 2 2
    5 2 3
    5 2 4
    5 3 1
    5 3 2
    5 3 3
    5 3 4
    5 4 1
    5 4 2
    5 4 3
    5 4 4
    12345701 2 1111111
    1111111121 65537 1111111111
    

    Sample Output

    0
    1
    3
    2
    0
    3
    1
    2
    0
    no solution
    no solution
    1
    9584351
    462803587
    

    Hint
    The solution to this problem requires a well known result in number theory that is probably expected of you for Putnam but not ACM competitions. It is Fermat’s theorem that states

       B(P-1) == 1 (mod P)
    
    
    for any prime P and some other (fairly rare) numbers known as base-B pseudoprimes. A rarer subset of the base-B pseudoprimes, known as Carmichael numbers, are pseudoprimes for every base between 2 and P-1. A corollary to Fermat's theorem is that for any m
    
       B(-m) == B(P-1-m) (mod P) .
    

    直接套模板

    code:

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <map>
    using namespace std;
    typedef long long ll;
    ll q_pow(ll a, ll b, ll mod){
        ll ans = 1;
        while(b){
            if(b & 1) ans = ans * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return ans;
    }
    
    ll gcd(ll a,ll b){
        return b ? gcd(b,a%b) : a;
    }
    
    void ex_gcd(ll a,ll b,ll &x,ll &y){
        if(!b){
            x = 1;
            y = 0;
            return;
        }
        ex_gcd(b,a%b,y,x);
        y -= a / b * x;
        return;
    }
    
    ll BSGS(ll a, ll b, ll p) {
        a %= p; b %= p;
        map<ll, ll> h;
        map<ll,bool> vis;//这道题必须多加一个map作为标记,否则直接查找会超时!!
        ll m = ceil(sqrt(p)), x, y, d, t = 1, v = 1;
        for(ll i = 0; i < m; ++i) {
            if(h.count(t)) h[t] = min(h[t], i);
            else h[t] = i,vis[t] = 1;
            t = (t*a) % p;
        }
        ex_gcd(t,p,x,y);
        ll inv = x > 0 ? x % p : x % p + p;
        for(ll i = 0; i < m; ++i) {
            if(vis[b]) return i*m + h[b];
            b = b * inv % p;
        }
        return -1;
    }
    int main(){
        ll b,p,n;
        while(~scanf("%lld%lld%lld",&p,&b,&n)){
            if(n >= p){
                puts("no solution");
                continue;
            }
            ll ans = BSGS(b,n,p);
            if(ans == -1) puts("no solution");
            else printf("%lld\n",ans);
        }
        return 0;
    }
    展开全文
  • 处理后得到R,那么这就是离散对数取模方程的求解过程了。 #include #include #include #include #include #include #include typedef long long ll; using namespace std; const int maxn = 510; const ll ...

    You have to color an M x N (1$ \le$M, N$ \le$108) two dimensional grid. You will be provided K (2$ \le$K$ \le$108) different colors to do so. You will also be provided a list of B (0$ \le$B$ \le$500)list of blocked cells of this grid. You cannot color those blocked cells. A cell can be described as (x, y), which points to the y-th cell from the left of the x-th row from the top.

    While coloring the grid, you have to follow these rules -

    1. You have to color each cell which is not blocked.
    2. You cannot color a blocked cell.
    3. You can choose exactly one color from K given colors to color a cell.
    4. No two vertically adjacent cells can have the same color, i.e. cell (x, y) and cell (x + 1, y) cannot contain the same color.

    \epsfbox{p11916.eps}

    Now the great problem setter smiled with emotion and thought that he would ask the contestants to find how many ways the board can be colored. Since the number can be very large and he doesn't want the contestants to be in trouble dealing with big integers; he decided to ask them to find the result modulo 100,000,007. So he prepared the judge data for the problem using a random generator and saved this problem for a future contest as a giveaway (easiest) problem.

    But unfortunately he got married and forgot the problem completely. After some days he rediscovered his problem and became very excited. But after a while, he saw that, in the judge data, he forgot to add the integer which supposed to be the `number of rows'. He didn't find the input generator and his codes, but luckily he has the input file and the correct answer file. So, he asks your help to regenerate the data. Yes, you are given the input file which contains all the information except the `number of rows' and the answer file; you have to find the number of rows he might have used for this problem.

    Input 

    Input starts with an integer T ( T$ \le$150), denoting the number of test cases.

    Each test case starts with a line containing four integers N, K, B and R (0$ \le$R < 100000007) which denotes the result for this case. Each of the next B lines will contains two integers x and y (1$ \le$x$ \le$M, 1$ \le$y$ \le$N), denoting the row and column number of a blocked cell. All the cells will be distinct.

    Output 

    For each case, print the case number and the minimum possible value of M. You can assume that solution exists for each case.

    Sample Input 

    4
    3 3 0 1728
    4 4 2 186624
    3 1
    3 3
    2 5 2 20
    1 2
    2 2
    2 3 0 989323
    

    Sample Output 

    Case 1: 3
    Case 2: 3
    Case 3: 2
    Case 4: 20
    题意:要给M行N列的网格染上K种颜色,其中有B个不用染色,其他每个格子涂一种颜色,同一列上下两个格子不能染相同的颜色,给出M,N,K,和B个格子的位置,求出涂色
    的方案%100000007的结果是R,现在给出N,K,R和B个格子位置,让你求最小的M
    思路:首先我们可以比较容易想到的是M最起码要和B个格子中X坐标最大的一样,然后我们尝试着一列一列的染色,每列从上到下染,如果一个格子是在第一行或者是在B个格子
    下面的话。那么就有K种可能,否则就是K-1种可能,现在我们将网格分成两部分,上面的部分是有B个坐标的不变的部分,下面是可变的部分,那么我们先计算出上面不变的部分
    和可变部分的第一行的和,然后每次添加一行的话就是增加(K-1)^N种可能。现在我们可以推出方程cnt*P^M = R,cnt是前面说的可以计算出来的,M是待增加的,在进行%
    处理后得到R,那么这就是离散对数取模方程的求解过程了。
    
    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <map>
    #include <set>
    #include <cmath>
    typedef long long ll;
    using namespace std;
    const int maxn = 510;
    const ll mod = 100000007;
    
    int n, m, k, b, r, x[maxn], y[maxn];
    set<pair<int, int> > best;
    
    ll mul_mod(ll a, ll b) {
    	return  a * b % mod;
    }
    
    ll pow_mod(ll a, ll p) {
    	ll tmp = 1;
    	while (p) {
    		if (p & 1)
    			tmp = tmp * a % mod;
    		p >>= 1;
    		a = a * a % mod;
    	}
    	return tmp;
    }
    
    void gcd(ll a, ll b, ll &d, ll &x, ll &y) {
    	if (!b) { d = a; x = 1; y = 0; }
    	else { gcd(b, a%b, d, y, x); y -= x*(a/b); }
    }
    
    ll inv(ll a) {
    	ll d, x, y;
    	gcd(a, mod, d, x, y);
    	return d == 1 ? (x+mod) % mod : -1;
    }
    
    int log_mod(int a, int b) {
    	int m, v, e = 1, i;
    	m = (int)sqrt(mod+0.5);
    	v = inv(pow_mod(a, m));
    	map<int, int> x;
    	x[1] = 0;
    	for (int i = 1; i < m; i++) {
    		e = mul_mod(e, a);
    		if (!x.count(e))
    			x[e] = i;
    	}
    	for (int i = 0; i < m; i++) {
    		if (x.count(b))
    			return i*m + x[b];
    		b = mul_mod(b, v);
    	}
    	return -1;
    }
    
    int count() {
    	int c = 0;
    	for (int i = 0; i < b; i++)
    		if (x[i] != m && !best.count(make_pair(x[i]+1, y[i]))) 
    			c++;
    
    	c += n;
    	for (int i = 0; i < b; i++)
    		if (x[i] == 1)
    			c--;
    
    	return mul_mod(pow_mod(k, c), pow_mod(k-1, (ll)m*n-b-c));
    }
    
    int doit() {
    	int cnt = count();
    	if (cnt == r) 
    		return m;
    
    	int c = 0;
    	for (int i = 0; i < b; i++)
    		if (x[i] == m)
    			c++;
    	m++;
    	cnt = mul_mod(cnt, pow_mod(k, c));
    	cnt = mul_mod(cnt, pow_mod(k-1, n-c));
    	if (cnt == r)
    		return m;
    
    	return log_mod(pow_mod(k-1, n), mul_mod(r, inv(cnt))) + m;
    }
    
    int main() {
    	int t, cas = 1;
    	scanf("%d", &t);
    	while (t--) {
    		scanf("%d%d%d%d", &n, &k, &b, &r);
    		best.clear();
    		m = 1;
    		for (int i = 0; i < b; i++) {
    			scanf("%d%d", &x[i], &y[i]);
    			if (x[i] > m)
    				m = x[i];
    			best.insert(make_pair(x[i], y[i]));
    		}
    		printf("Case %d: %d\n", cas++, doit());
    	}
    	return 0;
    }



     
    展开全文
  • 前三位就要用到对数函数:设n^k=a*10^m,(a) 那么a就表示n^k的缩小版,求出来直接放大100倍就行了; AC代码: #include #include typedef long long LL; LL quickpow(LL base,LL y,LL mod) { LL...
     

    1282 - Leading and Trailing

    Time Limit: 2 second(s)Memory Limit: 32 MB

    You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of nk.

    Input

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

    Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).

    Output

    For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that nk contains at least six digits.

    Sample Input

    Output for Sample Input

    5

    123456 1

    123456 2

    2 31

    2 32

    29 8751919

    Case 1: 123 456

    Case 2: 152 936

    Case 3: 214 648

    Case 4: 429 296

    Case 5: 665 669

     

    题意:求n^k的前三位数和后三位数;
     后三位好求,直接快速幂取模,但是要注意可能出现前导为0的情况,输出时应用格式控制;
    前三位就要用到对数函数:设n^k=a*10^m,(a<10) 那么a就表示n^k的缩小版,求出来直接放大100倍就行了;

    AC代码:

    #include<cstdio>
    #include<cmath>
    
    typedef long long LL;
    
    LL quickpow(LL base,LL y,LL mod)
    {
    	LL res=1;
    	while(y)
    	{
    		if(y&1)
    		{
    			res=res*base%mod;//不能写成res*=base%mod; 
    		}
    		y>>=1;
    		base=base*base%mod;
    	}
    	return  (res%mod+mod)%mod;
    }
    
    int main()
    {
    	LL T,N,bef,K,Kase=0;
    	double pre=0.0;
    	scanf("%lld",&T);
    	while(T--)
    	{
    		scanf("%lld %lld",&N,&K);
    		pre=1.0*K*log10(N*1.0);
    	    pre=pre-(LL)pre;
    		bef=quickpow(N,K,1000LL);
    		printf("Case %lld: %lld %03lld\n",++Kase,(LL)(pow(10.0,pre)*100),bef);//输出格式要注意 不够要补0 
    	}
    	return 0;
    }




    2016.12.9

    AC代码:
    #include<cstdio>
    #include<cmath>
    
    typedef long long LL;
    
    LL Pow_Mod(LL base,LL y,LL MOD) {
    	LL ans=1;
    	while(y) {
    		if(y&1) ans=ans*base%MOD;
    		y>>=1; base=base*base%MOD;
    	}
    	return ans;
    }
    int main() {
    	LL T,Kase=0; scanf("%lld",&T);
    	while(T--) {
    		LL N,K; scanf("%lld%lld",&N,&K);
    	    LL lest=Pow_Mod(N,K,1000); double tem=K*log10(N);
    		LL most=100*pow(10.0,tem-(LL)(tem));
    		printf("Case %lld: %lld %03lld\n",++Kase,most,lest); 
    	} 
    	return 0;
    }







     
    展开全文
  • 后三位好求点,用快速幂取模1000,就得到后三位了,但要注意模后不满三位要补上前导零。 前三位的话可以用对数来求。任意一个数n可以写成10 a 的形式,a为小数,则10 a = 10 x+y = 10 x * 10 y ,其中x为整数,...

    原题链接:传送门

    Description


    You are given two integers: n and k, your task is to find the most significant three digits, and least significant three digits of nk.

    Input


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

    Each case starts with a line containing two integers: n (2 ≤ n < 231) and k (1 ≤ k ≤ 107).

    Output


    For each case, print the case number and the three leading digits (most significant) and three trailing digits (least significant). You can assume that the input is given such that nk contains at least six digits.

    Sample Input


    5
    123456 1
    123456 2
    2 31
    2 32
    29 8751919

    Sample Output


    Case 1: 123 456
    Case 2: 152 936
    Case 3: 214 648
    Case 4: 429 296
    Case 5: 665 669


    题意:


    给你两个数 n 和 k,让你求出n^k的前三位和最后三位的数

    思路:


    后三位好求点,用快速幂取模1000,就得到后三位了,但要注意模后不满三位要补上前导零。
    前三位的话可以用对数来求。任意一个数n可以写成10a的形式,a为小数,则10a = 10x+y = 10x * 10y,其中x为整数,控制着n的位数,y为小数,决定着n的位数上的值。
    log10nk = k*log10n = a,fmod(a,1) 就是求a的小数部分y——决定n的位数上的值。再用pow(10,2+y),就是nk的前三位的值了。

    数学真的很奇妙啊

    PS:fmod(a,b)是对浮点数取余的函数,即a%b的值。其库函数是<math.h>
    #include <bits/stdc++.h>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    
    ll Pow(ll a,ll b,ll Mod){
        ll r = 1,base = a;
        while(b){
            if(b&1)
                r = base * r % Mod;
            base = base * base % Mod;
            b >>= 1;
        }
        return r % Mod;
    }
    
    int main(){
        int t;
        int n,k;
        int Case = 1;
        scanf("%d",&t);
        while(t--){
            scanf("%d%d",&n,&k);
    
            int first = pow(10.0 , 2.0 + fmod( k*log10(n*1.0) , 1) );
            int last = Pow(n % 1000 ,k ,1000);
    
            printf("Case %d: %d %03d\n",Case++,first,last);
    
        }
    
        return 0;
    }
    
    
    展开全文
  • 求符合某对严格递增序列对数 求反面即可 用到了每一个序列的minn maxx 每一个序列是否本身递增flag[i]=1 跳过 求不递增的序列 我的minn>=以我的minn及之前的数作为maxx的序列个数 #include<bits/stdc++.h> ...
  • 多项式乘,除(取模),求逆元: 例题–luoguP4512 #include&amp;lt;iostream&amp;gt; #include&amp;lt;cstdio&amp;gt; #include&amp;lt;algorithm&amp;gt; #include&amp;lt;cstring&...
  • 多项式除法及取模 已知 A ( x ) A(x) A ( x ) , B ( x ) B(x) B ( x ) ,求 C ( x ) C(x) C ( x ) , R ( x ) R(x) R ( x ) ,使得 A ( x ) = B ( x ) × C ( x ) + R ( x ) A(x)=B(x)\times C(x) +R(x) A ( x ) = ...
  • 取模运算的理解

    千次阅读 多人点赞 2019-07-17 16:42:19
    问题:在学习计算机组成中,不理解补码中取模运算的意义,故google一下,整理知识。 定义:模除(又称模数、取模操作、取模运算等,英语:modulo 有时也称作 modulus)得到的是一个数除以另一个数的余数。 公式:在...
  • 多项式求逆元 已知多项式 F ( x ) F(x) F ( x ) ,求 F ( x ) F(x) F ( x ) 在保留前n项(当然n要是2的次幂)的情况...多项式取模 已知 A ( x ) , B ( x ) A(x),B(x) A ( x ) , B ( x ) ,求 D ( x ) = A ( x ) m o...
  • 由于原根的性质,fi(mod)是原根关于mod的阶,那么此时fi(mod)就是最小的循环节,又由于mod是素数,那么mod的缩系就是完全剩余系,那么就可以覆盖所有正整数,那么较小的只需要打表求出所有的有关原根的离散对数,而...
  • 必须要取模long long装不下 for ( int i = 0;i < n;i ++ ) scanf ( "%lld", &a[i] ); polyln ( n, a, b ); for ( int i = 0;i < n;i ++ ) b[i] = b[i] * k %...
  • 取余与取模

    2020-12-31 11:13:30
    文章目录取余与取模取余取模整理使用案例 取余与取模 取余 取余运算,就是取左侧运算数除右侧运算数的余数的运算。 例如10取余3,商3余1,取余运算就是要余数的值,也就是取余结果为1。 如果除数是负数,也是一样的...
  • 快速幂取模

    2016-08-11 09:58:00
    快速幂取模 用法:用于求解 a 的 b 次方,而b是一个非常大的数,用O(n)的复杂度会超时。那么就需要这个算法,注意它不但可以对数求次幂,而且可用于矩阵快速幂。 假如求 x ^ n 次方 我们可以把 n 表示为 2^k1 +...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,856
精华内容 3,942
关键字:

对数取模