首页 > > 程序设计 > C/C++ >

<互测 day> 11.6 T1 谜团（mitua…

2018-06-17 21:36:43来源：未知阅读 ()

*PS： 没开long long被卡掉45分，果然出题人的话都不可信QAQ。。（学傻了）


与zqsz的互测题 T1 原题 POJ 1845


【题目描述】

谜团，是夜魇军团一名强大的战士。他来自远古，是一种不可思议的重力生命体，是来自原始黑暗的扭曲声音，在宇宙中的第一丝光线诞生前就存在的深渊化身。他能动用深渊之力将生物的身体污染，使之转化为自身的碎片“虚灵”。

“虚灵”为谜团所控，拥有一定的战斗力。更为恐怖的是，新产生的“虚灵”的 第一次攻击将吸收被攻击者内心的黑暗，从而分裂成若干个“虚灵”，之后的攻击将无法产生“虚灵”，新产生的“虚灵”第一次攻击仍可产生“虚灵”。 作为天辉军团智囊的你，需要知道某一时刻谜团最多可以产生多少“虚灵”，从而据

此来进行决策。具体的，谜团在 第一秒会转化一个单位，使之变成一个“虚灵”，由于能量消耗过大，谜团在之后的时间内将不再转化单位，使之变成“虚灵”。新产生的“虚灵”会在**下一秒**攻击一次，从而分裂出 m 个“虚灵”，原有的“虚灵”仍然存在，并且将不再产生虚灵。但新产生的“虚灵”可在下一秒攻击一次并分裂，之后也将不再产生“虚灵”（具体见样例解释）。给定时间 t 和分裂数 m，请你告诉天辉军团的战士们，在 t 秒后，谜团拥有多少个“虚灵”。

答案可能很大，要求你模一个数 k（不保证 k 是质数）。


【输入格式】

第一行：三个整数 m,t,k,意义见题目描述

【输出格式】

第一行：t 秒后谜团拥有的能量体个数

【样例输入 1】

3 3 1000

【样例输出 1】

13

【样例输入 2】

3 5 1000

【样例输出 2】

121

【样例 1 解释】

m = 3, t = 5 时：

第一秒：谜团制造 1 个“虚灵”

第二秒：1 个“虚灵”分裂出 3 个“虚灵”，此时共有 4 个“虚灵”

第三秒：第 1 秒制造的 1 个“虚灵”将不能分裂，第 2 秒制造的 3 个“虚灵”，

每个“虚灵”分裂成 3 个“虚灵”，新分裂出的“虚灵”有 9 个，此时共有 13

个“虚灵”。

最终，总共有 13 个“虚灵”

【数据规模与约定】

保证 k,m,t 及答案在 int 范围内（注意只有答案！！！）



原题意是求A^B的约数个数，因为出题人很良心（原话），所以就改为求首项为1，公比为m的等比数列的前n项和。

 部分分


1~8 暴力枚举


9~12 特殊性质：模数k是质数，因为等比数列的前n项和为 q^n-1/(q-1)，除法的取模需要用到逆元，可以用费马小定理做。

a^(p-1) ≡ 1(mod p) ---> a^(p-2) ≡ 1/a (mod p)

1 ll ans=(multiply(T,M)-1)%K*multiply(K-2,M-1)%K%K;
2 printf("%lld",ans);


13~16（原话）特殊性质 k不是质数，但k与m互质，用扩展欧几里得求逆元。

但是，我用的扩展欧几里得是要求m-1在%k意义下的逆元啊喂！！ 没有给部分分QAQ。

直接打exgcd可以的50分，前提是你开了long long ，但是我并没有开qwqqqq（让我自己一个人静一会）。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 long long M,T,K,ans;
 9 
10 long long multiply(long long n,long long a)
11 {
12     long long sum=1,x=a;
13     while(n)
14     {
15         if(n&1) sum=sum%K*x%K%K;
16         x=x%K*x%K%K;
17         n>>=1;
18     }
19     return sum%K;
20 }
21 long long exgcd(long long a,long long b,long long &x,long long &y)
22 {
23     if(b==0)
24     {
25         x=1,y=0;
26         return a;
27     }
28     long long d=exgcd(b,a%b,y,x);
29     y=y-a/b*x;
30     return d;
31 }
32 int main()
33 {
34     freopen("mituan.in","r",stdin);
35     freopen("mituan.out","w",stdout);
36     scanf("%lld%lld%lld",&M,&T,&K);
37     {
38         long long x,y;
39         long long d=exgcd(M-1,K,x,y);
40         x%=K;
41         while(x<0) x+=K/d;
42         ans=(multiply(T,M)-1)%K*x%K%K;
43         if(ans<0) ans+=K;
44         printf("%lld",ans);
45     }
46     return 0;
47 }

17~20 没有特殊性质

正解 1 公式求逆元

安利一个之前看到的博客（为什么我当时没有好好看qwq）

http://blog.csdn.net/acdreamers/article/details/8220787

因为费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求a与m互素。

但是我们有一个公式，若 b|a , 则ans即为（a/b）mod m 的答案：

证明：

（a/b）mod m = ans ；

a/b = ans + k * m ；

a = ans * b + k * m * b ；

a mod ( bm ) = ans * b ；

a mod ( bm ) / b = ans ；

得证。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define ull unsigned long long 
 8 
 9 ull M,T,K;
10 
11 ull multiply(ull n,ull a)
12 {
13     ull sum=1,x=a;
14     while(n)
15     {
16         if(n&1) sum=sum%K*x%K%K;
17         x=x%K*x%K%K;
18         n>>=1;
19     }
20     return sum%K;
21 }
22 int main()
23 {
24     freopen("mituan.in","r",stdin);
25     freopen("mituan.out","w",stdout);
26     scanf("%lld%lld%lld",&M,&T,&K);
27     K=K*(M-1);
28     ull ans=(multiply(T,M)-1)/(M-1);
29     printf("%lld",ans);
30     return 0;
31 }

正解 2 二分+递归

数学课上的求等比数列的前n项和有一个公式，emmm，公式有很多的变形，其中有一个变形为

若另 n 和 m 都等于 t/2 ，可知

所以我们要求St，只需要每次二分的递归下去，在递归的过程中取模就可以了。

另外注意递归的时候要分t为奇数和偶数的情况，因为计算机里的/是会自动下取整的。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define ll long long
 7 
 8 ll M,T,K;
 9 
10 ll pow(ll a,ll n)
11 {
12     ll sum=1,x=a;
13     while(n)
14     {
15         if(n&1) sum=sum%K*x%K%K;
16         x=x%K*x%K%K;
17         n>>=1;
18     }
19     return sum;
20 }
21 
22 ll sum(ll q,ll t) // q^0+q^1+q^2+...+q^t --> S(t+1)
23 {
24     if(t==0) return 1;
25     if(t%2==0) return (sum(q,t/2-1)%K*(1+pow(q,t/2))%K%K+pow(q,t)%K)%K; 
26     //t 为偶数，说明S(t+1)没法直接通过S((t+1)/2)求得，就去求St，最后加上一个q^t次方 
27     else return (sum(q,t/2)%K*(1+pow(q,t/2+1))%K)%K; 
28     //t 为奇数，说明S(t+1)可以直接用(S(t+1)/2)求得，又S((t+1)/2)即为sum(q,t/2)(t/2下取整)，可以直接求 (t/2+1即为(t+1)/2)  
29 }
30 int main()
31 {
32     freopen("mituan.in","r",stdin);
33     freopen("mituan.out","w",stdout);
34     scanf("%d%d%d",&M,&T,&K);
35     printf("%lld",sum(M,T-1));
36     return 0;
37 }