Bazinga 题解

第十四届浙江财经大学程序设计竞赛重现赛-B题

https://www.nowcoder.com/acm/contest/89/B

可能最近，脑子有问题，看见数论题都是秒，学弟问我这题怎么做，结果我沉思了几分钟，居然秒了

首先题意是求[l,r]内与k互质的数的乘积%k的值。

首先我知道两个比较简单的结论

结论1.：gcd(a+k,k)=gcd(a,k)

没错这就是更相减损法，如果你不认识的话，那应该认识这个算法的优化算法——辗转相除法。就是经常用来求GCD的那个算法。

这个算法给出了的一个重要的结论就是与k的互质的数，是以k为周期出现的。因为若gcd(a,k)=1,则gcd(a+k,k)还是1，也就是a与a+k.都与k互质

结论2：a*(a+k)*(a+2k)……*(a+mk)%k=a^(m+1)%k

这个结论比较好证，首先把每项都%k,你就会发现其实就是 a*a*a*a*a……*a=a^(m+1)%k

题解思路

枚举[1,k-1]内每个与互质的数a，然后算a,a+k,a+2k,a+3k,……中有多少个数落在[l,r].这个比较好求我就不详细讲了，假设最后算出来是m个。

则a的贡献就是a^m%k.。然后把所有数的贡献累乘一下就行了。

不论你是怎么实现的，写得再搓复杂度一般也在k*log(n)以内

因为时间给的比较多，所以我没加任何优化，直接硬上就过了。

 1 #include <stdio.h>
 2 #include<stack>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAXN 2000005
 6 #define  MAX 0
 7 using namespace std;
 8 long long qpow(long long a,long long n,long long mod)
 9 {
10     long long ans=1;
11     while(n)
12     {
13         if(n&1)
14             ans=ans*a%mod;
15         a=a*a%mod;
16         n>>=1;
17     }
18     return ans;
19 }
20 int cal(long long l,long long r,int k)
21 {
22     int i;
23     long long ans=1,m;
24     for(i=2; i<k&&i<=r; i++)
25     {
26         if(__gcd(i,k)==1)
27         {
28             m=(r+k-i)/k-(l+k-i-1)/k;
29             ans=ans*qpow(i,m,k)%k;
30         }
31     }
32     return ans;
33 }
34 int main()
35 {
36     long long l,r,k;
37     int i,j,t,cas=1;
38     scanf("%d",&t);
39     while(t--)
40     {
41         scanf("%lld%lld%lld",&l,&r,&k);
42         printf("Case #%d: ",cas++);
43         if(k==1)
44             puts("0");
45         else
46             printf("%d
",cal(l,r,k));
47 
48     }
49     return 0;
50 }

View Code