2019牛客ACM暑期多校第五场

A-digits 2

题目描述

You are given a positive integer n which is at most 100.

Please find a positive integer satisfying the following conditions:

1. The sum of all digits of this number is dividable by n.

2. This number is also dividable by n.

3. This number contains no more than 10410^4104 digits.
 

If such an integer doesn't exist, output "Impossible" (without quotation marks).

If there are multiple such integers, please output any one.

输入描述:

The first line contains one integer T indicating that there are T tests.

Each test consists an integer n in a single line.

* 1≤T≤1001 \le T \le 1001≤T≤100

* 1≤n≤1001 \le n \le 1001≤n≤100

输出描述:

For each query, output one line containing the answer. The number you print cannot have leading zeros. If there are multiple answers, you can print any. If such an integer doesn't exist, output "Impossible" (without quotation marks) in a single line.

示例1

输入

复制

3
1
9
12

输出

复制

1
666666
888

说明

For the last test, 888 is dividable by 12 (888 = 12 * 74) and 8 + 8 + 8 = 24 is also dividable by 12 (24 = 12 * 2).

题意：找到一个数是n的倍数&&这个数的所有数位之和是n的倍数

输出n个n（特判）

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            cout<<n;
        cout<<'\n';
    }
    return 0;
}

B-generator 1 矩阵快速幂（以10为单位倍增）

题目描述

You are given four positive integers x0,x1,a,bx_0, x_1, a, bx0​,x1​,a,b. And you know xi=a⋅xi−1+b⋅xi−2x_i = a \cdot x_{i-1} + b \cdot x_{i-2}xi​=a⋅xi−1​+b⋅xi−2​ for all i≥2i \ge 2i≥2.

Given two positive integers n, and MOD, please calculate xnx_nxn​ modulo MOD.

Does the problem look simple? Surprise! The value of n may have many many digits!

输入描述:

The input contains two lines.
The first line contains four integers x0,x1,a,bx_0, x_1, a, bx0​,x1​,a,b (1≤x0,x1,a,b≤1091 \le x_0, x_1, a, b \le 10^91≤x0​,x1​,a,b≤109).
The second line contains two integers n, MOD (1≤n<10(106),109<MOD≤2×1091 \le n < 10^{(10^6)}, 10^9 < MOD \le 2 \times 10^91≤n<10(106),109<MOD≤2×109, n has no leading zero).

输出描述:

Print one integer representing the answer.

示例1

输入

复制

1 1 1 1
10 1000000001

输出

复制

89

说明

The resulting sequence x is Fibonacci sequence. The 11-th item is 89.

示例2

输入

复制

1315 521 20185 5452831
9999999999999999999999999999999999999 1000000007

输出

复制

914730061

题意：给出f(0),f(1),a,b,n,mod   f(n)=a*f(n-1)+b*f(n-2)    求f(n)%mod

给了2s,显然用矩阵快速幂  学习一下：矩阵快速幂 &&  转移矩阵的推导

注意要以10为单位倍增，具体见注释

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll a0,a1,p,q,mod;

struct mat///2阶
{
    ll a[2][2];
};

mat mat_mul(mat x,mat y)///矩阵相乘
{
    mat res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                res.a[i][j]=(res.a[i][j]+(x.a[i][k]*y.a[k][j])%mod)%mod;
    return res;
}

mat mat_pow(mat x,ll n)
{
    if(n==1)
        return x;
    mat res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<2; i++)///{1 0} 单位阵
        res.a[i][i]=1;    ///{0 1}
    while(n)///快速幂
    {
        if(n&1)
            res=mat_mul(res,x);
        x=mat_mul(x,x);
        n>>=1;
    }
    return res;
//    return ((a0*res.a[0][0])%mod+(a1*res.a[0][1])%mod)%mod;///第一行和初始列矩阵{f(0),f(1)}的乘积==结果
}

int main()
{
    string s;
    while(scanf("%lld%lld%lld%lld",&a0,&a1,&p,&q)!=EOF)
    {
//        getchar();
        cin>>s>>mod;
        ll len=s.size();
        mat ans,c;
        memset(c.a,0,sizeof(c.a));
        memset(ans.a,0,sizeof(ans.a));
        c.a[0][0]=p;            ///转移矩阵 {p q}
        c.a[0][1]=q;            ///        {1 0}
        c.a[1][0]=1;
        ans.a[0][0]=ans.a[1][1]=1;///单位阵
        for(ll i=len-1; i>=0; i--)///从个位开始向前 每位对应转移矩阵的多少次方
        {
            ll tmp=s[i]-'0';
            if(tmp!=0)
                ans=mat_mul(ans,mat_pow(c,tmp));///pow过程中c不变
            c=mat_pow(c,10);///转移矩阵倍增 1次方 10次方 100次方……
        }
        cout<<((ans.a[1][0]*a1)%mod+(ans.a[1][1]*a0)%mod)%mod<<'\n';///乘了n个转移矩阵{f(n+1)}==(c^n)*{f(1)}
                                                                    ///                { f(n)}        {f(0)}
    }
    return 0;
}