3 条题解
-
2
这里提供一个不用龟速乘的方法,用 __int128 写。
#include<bits/stdc++.h> #define int long long #define I_love_ch ios::sync_with_stdio(0) #define China cin.tie(0) #define France cout.tie(0) #define ch_France return 0 using namespace std; void read(__int128& x){ int f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } x*=f; } void print(__int128 x){ if(x==0){ cout<<"0\n"; return; } bool f=0; if(x<0){ f=1; x=-x; } string s; while(x){ s.push_back(x%10+'0'); x/=10; } if(f) cout<<"-"; reverse(s.begin(),s.end()); cout<<s<<"\n"; } __int128 a,b,p; signed main(){ I_love_ch; China; France; read(a); read(b); read(p); int ans=((a%p)*(b%p))%p; print(ans); ch_France; } -
1
提供一个可以自由调整跑的快慢的做法。
调整参数TIM的值即可调控运行时长。
调到TIM=1e6时,大约200ms,稍微卡常来到160ms。
调到TIM=50~100并卡常+用c++14提交,可达17ms,力压sdjiaan的18ms做法。
此做法可以做到通过自由调控TIM的值,实现恰好T掉1个或4个或5个点,调到极限2.9*10^7,可以成功得到总耗时4077ms的满分做法。
#include <bits/stdc++.h> #define i32 int #define reg register #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("-Ofast") #pragma GCC optimize("inline") #define V 40 using namespace std; typedef __int128 ll; long long a, b, MOD; const ll exs = 1e18, TIM = 80; inline ll gsc(ll x, ll y, ll z) { if(y == 0) return 0; ll LIM = exs / x; if(LIM >= y) return x * y % z; ll cs = y / LIM, r = y % LIM, rs = 0; ll nm = x * LIM % z; ll mx = TIM, cc = cs / mx, rr = cs % mx; for(reg i32 pp=0; pp<mx; ++pp) rs = (rs + nm) % z; ll fn = gsc(rs, cc, z); for(reg i32 qq=0; qq<rr; ++qq) fn = (fn + nm) % z; fn = (fn + x * r % z) % z; return fn; } void print(ll t) { int W[V], dx = 0; if(t == 0) { cout << 0; return; } while(t) { W[++dx] = t % 10, t /= 10; } for(reg i32 i=dx; i>0; --i) cout << W[i]; } i32 main() { ios :: sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> a >> b >> MOD; a %= MOD, b %= MOD; print(gsc(a, b, MOD)); return 0; } -
-1
楼下的int128虽然很有脑,但还是太吃操作了,居然还要用快读(不会快读的同学感到很赞)我觉得可以在操作的时候强转int128然后输出的时候再转回来就可以了(除非输入输出也超过long long)代码如下:
using namespace std; typedef long long ll; __int128 solve(__int128 a,__int128 b,__int128 p){ return (a%p)*(b%p)%p; } int main(){ ll a,b,p; cin>>a>>b>>p; ll res=(ll)solve((__int128)a,(__int128)b,(__int128)p); cout<<res; return 0; }然后给出一个龟速乘的正常做法: (感觉没什么好讲的就和快速幂差不多)
#include<bits/stdc++.h> using namespace std; typedef long long ll; //核心思想:将乘法转化为加法。利用b的二进制展开,例如a*13=a*8+a*4+a*1 ll solve(ll a,ll b,ll p){ ll ans=0; for(;b;b>>=1){//当b>0时循环,每次循环b右移一位(相当于b/=2) if(b&1)ans=(ans+a)%p;//检查b的最低位是否为1,如果为1,则将当前的a累加到结果中,并取模防止溢出 a=a*2%p;//底数翻倍 } return ans; } int main(){ ll a,b,p; cin>>a>>b>>p; cout<<solve(a,b,p); return 0; }这是本蒟蒻发的第一篇题解,各位dalao、老师多多包涵QwQ
- 1
信息
- ID
- 823
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 64
- 已通过
- 14
- 上传者