牛客多校第五场

发表于 | 更新于 | 分类于

A digits 2

签到题

B generator 1

题意

思路

构造矩阵,十进制矩阵快速幂,在对每位进行二进制快速幂.

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+20;
ll mod;
char n[maxn];
int _size;
struct Matix{
    ll m[3][3];
    Matix(){
        memset(m, 0, sizeof(m));
    }
    Matix operator*(const Matix &m2){
        Matix t;
        for (int i = 0; i < _size; ++i) //不能写小于MAXN
            for (int j = 0; j < _size; ++j)
                for (int k = 0; k < _size; ++k)
                    t.m[i][j] = (t.m[i][j] + m[i][k] * m2.m[k][j]) % mod;
        return t;
    };
    Matix operator^(ll k) {
        Matix x = *this, ans;
        ans.m[0][0] = ans.m[1][1] = 1;
        while (k) {
            if (k&1)
                ans = ans * x;
            x = x * x;
            k >>= 1;
        }
        return ans;
    }
}g,res;
int main(){
    ll x0,x1,a,b;
    scanf("%lld%lld%lld%lld",&x0,&x1,&a,&b);
    scanf("%s%lld",n,&mod);
    _size=2;
    g.m[0][0]=a,g.m[0][1]=1,g.m[1][0]=b,g.m[1][1]=0;
    int len=strlen(n);
    res.m[0][0]=x1,res.m[0][1]=x0;
	res.m[1][0]=0,res.m[1][1]=0;
    ll ans=0;
    for(int i=len-1;i>=0;--i){
        if(n[i]!='0')res=res*(g^(n[i]-'0'));
        g=g^10;
    }
    printf("%lld\n",res.m[0][1]);
	//system("pause");
    return 0;
}

C generator 2

题意

给出n,$x_0$,a,b,p求$x_i=(ax_{i-1}+b)$%p,再给出q次查询,每次给出v,求出最小的下标使得$x_i$=v,s输出下标

思路

根据$x_i=ax_{i-1}+b$推导除$x_n=a^nx_0+a^{n-1}b+a^{n-2}b+….+ab+b$再根据等比数列合并得 ‘$ a^n=\frac{v*(a-1)+b}{(a-1)x_0+b}$’=v ,下面这部分用逆元求,在用SGBG,形如$a^n$=b(mod p) ,n=i*t-j,t=1e6 ,i=[0,1e3+10],j=[0,1e3+10].在考虑特殊情况a=1,a=0的情况,这道题就解决完成了.

代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod,t1=1e3,t2=1e6;
unordered_map<int,int> Hash;
ll  ksm(ll a, ll p, ll mod) {
	a%=mod;
    ll base=1;
    while(p) {
        if(p&1) base=base*a%mod;
        a=a*a%mod; 
		p>>=1;
    }
    return base;
}
int main(){
	int _;
	scanf("%d",&_);
	while(_--){
		Hash.clear();
		ll n,x0,a,b;
		int q;
		scanf("%lld%lld%lld%lld%d%d",&n,&x0,&a,&b,&mod,&q);
		ll aj=ksm(a,t1,mod);
		ll val=1;
		for(int i=1;i<=t2;i++){
			val=val*aj%mod;
			if(!Hash.count(val)) Hash[val]=i*t1;
		}
		ll temp=((a-1)*x0%mod+b)%mod;
		ll fz=ksm(temp,mod-2,mod);
		while(q--){
			ll v;
			scanf("%lld",&v);
			if(a==0){
				if(v==x0) printf("0\n");
				else if(v==b) printf("1\n");
				else printf("-1\n");
			}
			else if(a==1){
				ll ans=((v-x0)%mod+mod)%mod*ksm(b,mod-2,mod)%mod;
				if(ans<n) printf("%lld\n",ans);
				else printf("-1\n");
			}
			else {
				int ans=mod+1;
				v=(v*(a-1)%mod+b)%mod*fz%mod;
				val=v;
				for(int i=0;i<=t1;i++){
					if(Hash.count(val)) ans=min(ans,Hash[val]-i);
					val=val*a%mod;
				}
				if(ans==mod+1||ans>=n) printf("-1\n");
				else printf("%d\n",ans);
			}
		}
	}
	//system("pause");
}