B.Icebound and Sequence

落日映苍穹つ 2021-12-23 11:37 151阅读 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 条评论，151人围观）

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

相关阅读

相关 sequences

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

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

相关 sequence to sequence

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

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

相关关联规则挖掘算法-CATS Tree(Compressed and Arranged Transaction Sequences Tree)

CATS Tree 压缩排序事务树 FPTree的一个扩展允许单路径频繁模式挖掘适用于多种支持度、流数据、增量数据的情况算法基本过程数据集

小咪咪/ 2022年06月05日 23:25/ 0 赞/ 133 阅读

相关 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 赞/ 149 阅读

相关 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 赞/ 155 阅读

相关 AVC sequence header & AAC sequence header

推送H.264和AAC的重要前提 RTMP的音视频流的封装形式和FLV格式相似, 流媒体服务器向客户端发送包含H264和AAC的RTMP直播流，需要首先发送: AVC

素颜马尾好姑娘i/ 2022年04月03日 03:24/ 0 赞/ 224 阅读

相关 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 赞/ 137 阅读

相关 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 赞/ 152 阅读

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

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

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

相关 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 赞/ 321 阅读