3 条题解

  • 2
    @ 2026-9-7 14:11:10

    这里提供一个不用龟速乘的方法,用 __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
      @ 2026-11-13 15:54:21

      提供一个可以自由调整跑的快慢的做法。

      调整参数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
        @ 2026-9-7 14:28:01

        楼下的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
        上传者