B.Icebound and Sequence

比眉伴天荒 2022-01-10 05:13 189阅读 0赞

### 链接:[https://ac.nowcoder.com/acm/contest/903/B][https_ac.nowcoder.com_acm_contest_903_B] ###

### 题意： ###

Icebound hates math. But Imp loves math. One day, Imp gave icebound a problem.  
  
The problem is as follows.  
  
S=(∑ni=1qi） mod pS=(∑i=1nqi） mod p  
  
For given q,n,p, you need to help icebound to calculate the value of S.

### 思路： ###

等比数列求和。

因为考虑到取余，所以不能直接算。

令S(n) 为等比数列前n项和。

若n为偶数：

S(n) = S(n/2) + S(n/2)\*a^(n/2) (因为第i(i <= n/2)项和i+n/2项存在第i项乘a^(n/2)等以第i+n/2项的值。

若n为奇数：

S(n) = S(n/2) + S(n/2)\*a^(n/2) + a^n

### 代码： ###

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long LL;
    
    LL n, q, p;
    
    LL QM(LL a, LL b, LL m)
    {
        LL res = 1;
        while (b)
        {
            if (b&1)
                res = (res*a)%m;
            a = (a*a)%m;
            b >>= 1;
        }
        return res;
    }
    
    LL GetR(int t)
    {
        if (t == 1)
            return n%p;
        if (t%2 == 0)
            return (GetR(t/2)+(GetR(t/2)*QM(n, t/2, p))%p)%p;
        else
            return ((GetR(t/2)+(GetR(t/2)*QM(n, t/2, p))%p)%p+QM(n, t, p))%p;
    }
    
    int main()
    {
        int t;
        cin >> t;
        while (t--)
        {
            cin >> n >> q >> p;
            cout << GetR(q) << endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10923486.html

[https_ac.nowcoder.com_acm_contest_903_B]: https://ac.nowcoder.com/acm/contest/903/B

发表评论取消回复

表情：

评论列表（有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读

相关 sequences

1 内存库（SMDB）修改sequences OCS割接一般涉及的内存库sequences 日志相关表： OCS\_RECHARGELOG\_I.

落日映苍穹つ/ 2023年08月17日 15:53/ 0 赞/ 153 阅读

相关 The Child and Sequence （线段树取模）

题意：线段树取模操作，维护两个数组，一个维护当前区间的最大值，一个维护当前区间的和，如果最大值小于mod，就不用再往下取模了；单点更新，区间查找正常操作~；；； ![Cont

浅浅的花香味﹌/ 2023年06月03日 13:00/ 0 赞/ 19 阅读

相关 HDOJ 5504-GT and sequence

GT and sequence Accepts: 95 Submissions: 1467 Time Limit: 2000/1000 MS (Java/Others

秒速五厘米/ 2022年08月20日 02:18/ 0 赞/ 55 阅读

相关 sequence to sequence

[论文 Sequence to Sequence Learning with Neural Networks][Sequence to Seque

Myth丶恋晨/ 2022年07月15日 10:39/ 0 赞/ 441 阅读

相关 PAT甲级-1140. Look-and-say Sequence (20)（模拟）

1140. Look-and-say Sequence (20) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B

港控/mmm°/ 2022年05月29日 06:15/ 0 赞/ 198 阅读

相关 1140. Look-and-say Sequence (20)

Look-and-say sequence is a sequence of integers as the following: D, D1, D111, D113

男娘i/ 2022年05月28日 08:54/ 0 赞/ 207 阅读

相关 B.Icebound and Sequence

链接:[https://ac.nowcoder.com/acm/contest/903/B][https_ac.nowcoder.com_acm_contest_903_B]

比眉伴天荒/ 2022年01月10日 05:13/ 0 赞/ 190 阅读

相关 B.Icebound and Sequence

链接:[https://ac.nowcoder.com/acm/contest/903/B][https_ac.nowcoder.com_acm_contest_903_B]

落日映苍穹つ/ 2021年12月23日 11:37/ 0 赞/ 195 阅读

相关 CodeForces 438D The Child and Sequence（线段树）

题目链接：[http://codeforces.com/problemset/problem/438/D][http_codeforces.com_problemset_pro

清疚/ 2021年11月01日 17:58/ 0 赞/ 272 阅读

相关 1455D Sequence and Swaps（思维）

D. Sequence and Swaps time limit per test 1.5 seconds memory limit per test

本是古典何须时尚/ 2021年07月16日 18:42/ 0 赞/ 376 阅读