赚钱买房（java大数+逆元+等比数列求和+快速幂）

客官°小女子只卖身不卖艺 2022-08-02 02:20 110阅读 0赞

![20150706190210233][]

**这一题的思想就是等比数列求和，求和过程中需要用到快速幂方法！**

**求完和之后对这个数求模!求模用到了逆元，什么是逆元呢？**

今天我们来探讨逆元在**ACM-ICPC**竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。

对于正整数![20140613102654328][]和![20140613102712781][]，如果有![20140613102734984][]，那么把这个同余方程中![20140613102856531][]的最小正整数解叫做![20140613102654328][]模![20140613102712781][]的逆元。

逆元一般用扩展欧几里得算法来求得，如果![20140613102712781][]为素数，那么还可以根据费马小定理得到逆元为![20140613103413828][]。

推导过程如下

![20140613104248984][]

求现在来看一个逆元最常见问题，求如下表达式的值**（已知![20140613104752312][]）**

![20140613104619203][]

当然这个经典的问题有很多方法，最常见的就是扩展欧几里得，如果![20140613102712781][]是素数，还可以用费马小定理。

但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求![20140613102654328][]与![20140613102712781][]互素。实际上我们还有一

种通用的求逆元方法，适合所有情况。公式如下

![20140613105646406][]

现在我们来证明它，已知![20140613104752312][]，证明步骤如下

![20140613112023328][]

这个就是逆元！

![20150706190753567][]  
这个公式就是我们要求的数！  
  
逆元就想上面哪个公式求！

#include<cstdio>
    #include<cmath>
    #include<iostream>
    #define ll long long
    using namespace std;
    ll pow_mod(ll a,ll n,ll m)
    {
        ll ans = 1;
        a = a % m;
        while(n>0)
        {
            if(n%2 ==1)
                ans=(ans*a)%m;
            n=n/2;
            a=(a*a) % m;
        }
        return ans;
    }
    int main()
    {
        ll a,n,b,sum1,sum2,i,sum3;
        while(scanf("%lld%lld%lld",&a,&n,&b)!=EOF)
        {
           sum1=9*b;
           cout<<"模式:"<<pow_mod(10,n,sum1)<<endl;
           sum3=(pow_mod(10,n,sum1)-1%sum1)%sum1;
           cout<<sum3<<endl;
           sum2=((a%sum1)*(sum3%sum1))%sum1;
           sum2/=9;
           cout<<b-sum2<<endl;
        }
    }
    /*
    0 9999999 2147483646
    5 9999999  456465465
    2012456840 1000 3
    2054879653 1000 546813
    2147483646 0 54
    4568 9999999 5687
    68456213 9999999 2147483646
    9999999 9999999 9999999
    
    2147483646
    109893150
    1
    230594
    54
    2219
    326455227
    9999999
    */

C++在运算过程中超了ll的值，所以我们需要重新想办法！  
  
这里我用了java大数！正好连第二题也给过了！

import java.math.BigInteger;
    import java.util.Scanner;
    import java.math.*;
    public class Main {
    	public static void main(String[] args)
    	{
    		Scanner cin=new Scanner(System.in);
    		BigInteger sum2,a,b,sum1,sum3;
    		int n;
    		while (cin.hasNext()) 
    		{
    			a=cin.nextBigInteger();
    			n=cin.nextInt();
    			b=cin.nextBigInteger();
    			sum1=BigInteger.valueOf(9).multiply(b);
    			sum3=(pow_mod(BigInteger.valueOf(10),n,sum1).subtract((BigInteger.valueOf(1).remainder(sum1)))).remainder(sum1);
    			sum2=((a.remainder(sum1)).multiply(sum3.remainder(sum1))).remainder(sum1);
    			sum2=sum2.divide(BigInteger.valueOf(9));
    			System.out.println(b.subtract(sum2));
    		}
    		
    	}
    	private static  BigInteger pow_mod(BigInteger a, int n,BigInteger m) 
    	{
    		BigInteger ans = BigInteger.valueOf(1);
    	    a = a.remainder(m);
    	    while(n>0)
    	    {
    	        if(n%2 ==1)
    	            ans=(ans.multiply(a)).remainder(m);
    	        n=n/2;
    	        a=a.multiply(a).remainder(m);
    	    }
    	    return ans;
    		
    	}
    }

发一下第二题的题目！  
![20150706191213162][]  
ok！呵呵！

[20150706190210233]: /images/20220731/616de6791e5e43e3bad52b55a2d2b094.png
[20140613102654328]: https://img-blog.csdn.net/20140613102654328
[20140613102712781]: /images/20220731/13d616ab2e7643cea5c06083dea96d4a.png
[20140613102734984]: https://img-blog.csdn.net/20140613102734984
[20140613102856531]: https://img-blog.csdn.net/20140613102856531
[20140613103413828]: /images/20220731/f5fb664b408c495ca01f830654688840.png
[20140613104248984]: /images/20220731/b4c4482274fc423bb18323683c6a5c01.png
[20140613104752312]: /images/20220731/1924e93e72b94b81aa6fa87e0420f627.png
[20140613104619203]: /images/20220731/4039e0da930d4d4f89a2407fdae0b657.png
[20140613105646406]: /images/20220731/e967cd9a54904ab4aace46b7a42a3e8f.png
[20140613112023328]: /images/20220731/147b6e144dec47fcad6529877a7d11f6.png
[20150706190753567]: /images/20220731/76dc886f52bf4308979ddd163ab8bb97.png
[20150706191213162]: /images/20220731/5799081719e549a18643e960446d4762.png