wannafly camp day4

2088: 电音之王

描述

题目描述：

终于活成了自己讨厌的样子。

听说多听电音能加快程序运行的速度。

定义一个数列，告诉你a0,a1,m0,m1,ca\_0,a\_1,m\_0,m\_1,ca0,a1,m0,m1,c，定义an=m0an−1+m1an−2+ca\_n=m\_0a\_{n-1}+m\_1a\_{n-2}+can=m0an−1+m1an−2+c对所有n≥2n\geq 2n≥2。

求(∏i=0kai)modM\left( \prod\_{i=0}^{k}{a\_i} \right) mod M(∏i=0kai)modM

输入：

第一行一个整数T(1≤T≤1000)T(1\leq T\leq 1000)T(1≤T≤1000)，表示数据组数。

每组数据一行777个整数a0,a1,m0,m1,c,M,ka\_0,a\_1,m\_0,m\_1,c,M,ka0,a1,m0,m1,c,M,k，保证1≤M≤1018,0≤a0,a1,m0,m1,c<M,2≤k≤1061\leq M\leq 10^{18},0\leq a\_0,a\_1,m\_0,m\_1,c< M, 2\leq k\leq 10^61≤M≤1018,0≤a0,a1,m0,m1,c<M,2≤k≤106，保证MMM为奇数。

保证∑k≤108\sum k \leq 10^8∑k≤108。

输出：

对于每组数据，输出一行表示答案。

样例输入

1
1 1 1 1 0 1000000007 10

样例输出

904493530

题意 ： 就是按照要求求几个数册乘积并取模，注意他这里的模数非常的大，普通的边乘边取模直接或炸掉，因此这里可以用一个快速乘，当相乘的两个数大于long long 时仍然可以保证答案的正确性
代码示例 ：

using namespace std;

#define ll long long

const int maxn = 1e6+5;

const int mod = 1e9+7;

const double eps = 1e-9;

const double pi = acos(-1.0);

const int inf = 0x3f3f3f3f;

ll a0, a1, m0, m1, c, M, k;

inline ll multi(ll x,ll y,ll mod){

    x = x%mod, y = y % mod;

    return ((x*y-(ll)(((long double)x*y+0.5)/mod)*mod)%mod+mod)%mod;

}

int main() {

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

    //freopen("out.txt", "w", stdout);

    int t;

    cin >>t;

    while(t--){

        scanf("%lld%lld%lld%lld%lld%lld%lld", &a0, &a1, &m0, &m1, &c, &M, &k);

        a0 %= M, a1 %= M, m0 %= M, m1 %= M, c %= M;

        ll ans = multi(a0, a1, M);

        for(int i = 2; i <= k; i++){

            ll x = ((multi(m0, a1, M)+multi(m1, a0, M))%M + c)%M;

            ans = multi(ans, x, M);

            a0 = a1, a1 = x;

        }

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

    }

    return 0;

}

2098: 数论之神

描述

题目描述：

终于活成了自己讨厌的样子。

这是她们都还没长大的时候发生的故事。那个时候，栗子米也不需要为了所谓的爱情苦恼。

她们可以在夏日的午后，花大把的时间去研究生活中一些琐碎而有趣的事情，比如数论。

有一天西柚柚问了栗子米一个题，她想知道⌊n1⌋,⌊n2⌋,…,⌊nn⌋\lfloor\frac{n}{1}\rfloor, \lfloor\frac{n}{2}\rfloor, \dots, \lfloor\frac{n}{n}\rfloor⌊1n⌋,⌊2n⌋,…,⌊nn⌋中有多少不同的数，这些不同的数字里面第kkk大的是多少。

输入：

第一行一个整数T(T≤105)T(T\leq 10^5)T(T≤105)，表示数据组数。

每组数据第一行两个整数，表示n,k(1≤n≤1018)n,k(1\leq n\leq 10^{18})n,k(1≤n≤1018)，保证kkk不会超过不同的数字个数。

输出：

对于每组数据输出，输出两个整数，表示有多少个不同的数字和这里面第k大的是多少。

样例输入

样例输出

1 1
3 2
15 8

题目分析 ： 找规律发现一定是1, 2, 3, ..., x, n/(x-1), n/(x-2), .... x是sqrt(n)附近
代码示例 ：

#include<bits/stdc++.h>

#include<algorithm>

using namespace std;

#define ll long long

ll n, k;

ll ff;

int main() {

    ll t;

    cin >> t;

    while(t--){

    	scanf("%lld%lld", &n, &k);

		ll f;

        ll l = 1, r = 1000000000;

        while(l <= r){

            ll mid = (l+r)>>1;

            if (mid*mid <= n) {

                f = mid;

                l = mid+1;

            }

            else r = mid-1;

        }

		ll ans = 2*f;

		if (f == n/f) ans--;

        ll ans2;

        ll k1 = ans-k+1; // 第 K 小

        if(k1 <= f)  ans2 = k1;

        else ans2 = n/k;

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

    }

    return 0;

}

巴特西

wannafly camp day4

2088: 电音之王

题目描述：

输入：

输出：

2098: 数论之神

题目描述：

输入：

输出：

最新文章

热门文章