【阔别许久的博】【我要开始攻数学和几何啦】【高精度取模+同余模定理，*】POJ 2365 The Embarrassed Cryptographer

题意：给出一大数K(4 <= K <= 10^100)与一整数L(2 <= L <= 10⁶)，K为两个素数的乘积(The cryptographic keys are created from the product of two primes)

　　　问构成K的最小素数是否绝对小于L，若是，则输出BAD p，p为最小素数，否则输出GOOD;

分析：从小到大枚举1~10^6内的素数p，while(p<L)时，判断K是否能被p整除，若能则证明构成K的最小素数绝对小于L，反之则大于L；

Tags:1、素数打表

　　　　注意打表时要求最大的素数大于10^6，否则在循环while(p<L)会造成死循环

　　　2、大整数char/string形式输入；

　　　3、所谓同余模定理其最常见的应用就是：(a+b)%n = a%n+b%n; (a*b)%n=(a%n*b%n)%n;

　　　4、大整数取模算法同样适用于高进制的情况（本题为千进制），注意将K转换为千进制时的优化，否则很容易TLE；本题使用的方法为“局部有序，全局倒序”，即

　　　　K = 12345678910 = [910][678][345][12];这样则可以利用以下方式求得

 for(int i = ; i < len; i++)

 {

     int pos = (len+-i)/-;

     kt[pos] = kt[pos]*+(k[i]-'');

 }

 cnt = (len+)/;

 bool BI_Mod(int x)

 {

     int ans = ;

     for(int i = cnt-; i >= ; i--)

     {

         ans = (int)(((LL)ans*+kt[i])%x);

     }

     return ans;

 }

巴特西

【阔别许久的博】【我要开始攻数学和几何啦】【高精度取模+同余模定理，*】POJ 2365 The Embarrassed Cryptographer

最新文章

热门文章