【CodeChef】Just multiply
发布时间
阅读量：
阅读量
该文本讨论了如何高效地进行大数运算（如模运算）以及如何优化快速幂算法的实现方式。涉及的内容包括：
模运算：通过mul和Pow等函数实现高效的乘法和幂次计算。
字符串处理：将字符串中的数字提取并用于计算。
快速幂算法：通过位操作优化幂次计算的速度。
模指数循环节：探讨如何避免直接取模导致的性能问题，并提供了解决方案。
这些内容的核心在于优化大数运算效率，并在实际应用中减少直接取模带来的性能损失。
数据水
讲道理，指数循环节不能直接取模
#include<bits/stdc++.h>
using namespace std;
char inc;
inline void get(int& x)
{
x = 0;inc = getchar();
while(!isdigit(inc))inc=getchar();
while(isdigit(inc))
{
x=x*10+inc-'0';
inc=getchar();
}
}
#define maxn 10010
int T,mod,len;typedef long long ll;
char s[maxn];
ll mul(ll x,ll p)
{
if(x==0)return 0;
if(p==0)return 1;
ll t = x,ret=1;
while(p)
{
if(p&1)ret*=t;
t*=t;
t%=mod;
ret%=mod;
p>>=1;
}
return ret;
}
int main()
{
get(T);
while(T--)
{
get(mod);scanf("%s",s);
len = strlen(s);
ll last = 1;bool flag = false;
ll fir = 0,sec = 0;
for(int i=0;i<len;i++)
{
if(s[i]!='*')
{
if(!flag)fir = (fir*10+s[i]-'0')%mod;
else sec = (sec*10+s[i]-'0')%mod;
}
else
{
if(s[i+1]=='*')
{
i=i+1;
flag = true;
}
else
{
if(flag)
{
last = last*(mul(fir,sec)%mod)%mod;
fir = sec = 0;
flag = false;
}
else
{
last = last*fir%mod;
fir = 0;
flag = false;
}
}
}
}
if(flag)last = last*(mul(fir,sec)%mod)%mod;
else last = last*fir%mod;
printf("%lld\n",last);
}
return 0;
}一种神奇的方法
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define ll long long
using namespace std;
char s[10010];
ll m;
ll mul(ll a,ll b) {
ll ret=0;
while(b) {
if(b&1) ret=(ret+a)%m;
a=(a<<1)%m; b>>=1;
}return ret;
}
ll Pow(ll a,ll b) {
ll ret=1;
while(b) {
if(b&1) ret=mul(ret,a);
a=mul(a,a); b>>=1;
}return ret;
}
ll Pow(string b, string e) {
ll t=0;
for(int i=0;i<b.length();++i) t=mul(t,10)+b[i]-'0';
ll ret=1%m;
for(int i=e.length()-1;~i;--i) {
ret=mul(ret,Pow(t,e[i]-'0'));
t=Pow(t,10);
}return ret;
}
void Work() {
scanf("%lld%s",&m,s);
ll ans=1%m; char *p=s,*r,*q;
while(true) {
for(q=p;isdigit(*q);++q);
for(r=q+2;isdigit(*r);++r);
ans=mul(ans,Pow(string(p,q),string(q+2,r)));
if(*r=='\0') break;
p=r+1;
} printf("%lld\n",ans);
}
int main() {
int T; scanf("%d",&T);
while(T--) Work();
return 0;
} 2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int T;
ll M;
char ch[10005];
ll mul(ll a,ll b)
{
ll ans=0;a%=M;
for(ll i=b;i;i>>=1,a=(a+a)%M)
if(i&1)ans=(ans+a)%M;
return ans%M;
}
ll qpow(ll a,ll b)
{
ll ans=1;a%=M;
for(ll i=b;i;i>>=1,a=mul(a,a))
if(i&1)ans=mul(ans,a);
return ans%M;
}
ll pow(int a,int b,int c,int d)
{
ll tmp=0,ans=1;
for(int i=a;i<=b;i++)
tmp=(mul(tmp,10)+ch[i]-'0')%M;
for(int i=c;i<=d;i++)
{
ans=mul(qpow(ans,10),qpow(tmp,ch[i]-'0'));
}
return ans;
}
ll solve(ll l,ll r,ll num)
{
for(int i=r;i>=l;i--)
if(ch[i]=='*')
{
if(ch[i-1]!='*')return mul(solve(l,i-1,1),solve(i+1,r,num));
else
{
int j=i-2;
while(ch[j]!='*'&&j)j--;
ll res=pow(j+1,i-2,i+1,r);
if(j==0)return res;
if(ch[j-1]=='*')return solve(l,j-2,res);
else return mul(solve(l,j-1,1),res);
}
}
ll tmp=0;
for(int i=l;i<=r;i++)tmp=(mul(tmp,10)+ch[i]-'0')%M;
if(num==1)return tmp;
else return qpow(tmp,num);
}
int main()
{
T=read();
while(T--)
{
M=read();
scanf("%s",ch+1);
int l=strlen(ch+1);
printf("%lld\n",solve(1,l,1));
}
return 0;
}全部评论 (0)
还没有任何评论哟~