洛谷题解 P2312 【解方程】-白红宇

洛谷题解 P2312 【解方程】

阅读量：4308 次

发布时间：2019-06-06

本文共 2981 字，大约阅读时间需要 9 分钟。

Problem

P2312 【解方程】

record

用时： 1166ms

空间： 780KB(0.76MB)

代码长度： 2.95KB

提交记录： R9909587

注：使用了
1. o1 优化
2. o2 优化
3. o3 优化
4. 快读快输

Solution

30 pts

枚举，使用 int，直接按题目所说~~暴力乱搞一通~~

Unaccepted 30Ac:3Wa:7

50 pts

∣a_i∣≤10^10000

所以高精度。

然而慢的一皮：

Unaccepted 50Ac:5Tle:5

评测记录

30 pts

考虑暴力优化。

考虑在模意义下进行暴力，可以减小误差。

注意：模的应该是质数，且应该多模数，防止误差。

质数应该多记住几个，考场上的时候很有用（如：哈希）

然后。。。就出锅了。

评测记录

Unaccepted 30Ac:3Wa:7

100 pts

请大家在NOIp上一定要：开 long long！

评测记录

Accepted 100Ac:10

Code

// luogu-judger-enable-o2/** * Problem: P2312 解方程.  * Author:  航空信奥.  * Date:    2018/08/19.  * Upload:  Luogu.  */#pragma GCC optimize("O1")#pragma GCC optimize("O2")#pragma GCC optimize("O3")#include 
    
     #include 
     
      using namespace std;namespace hkxadpall {    char BufferRead[1 << 15];    int rLen = 0, rPos = 0;    inline char Getchar()    {        if (rPos == rLen) rPos = 0, rLen = fread(BufferRead, 1, 1 << 15, stdin);        if (rPos == rLen) return EOF;        return BufferRead[rPos++];    }         template 
      
        inline _TpInt read();    template 
       
         inline void write(_TpInt x);    #   define Max_N 103#   define Mod1  10007LL#   define Mod2  19260817LL#   define Mod3  100000007LL        int n, m;    long long a1[Max_N];    long long a2[Max_N];    long long a3[Max_N];        bool isRight(long long *a, int x, long long mod)    {        long long ans = a[n];        for (int i = n - 1; i >= 0; i--) {            ans = (ans * x + a[i]) % mod;        }        return (ans == 0);    }        int main()     {           n = read
        
         ();        m = read
         
          (); for (int i = 0; i <= n; i++) { bool flag = 0; char c = Getchar(); while ((c > '9' || c < '0') && c != '-') c = Getchar(); if (c == '-') flag = 1, c = Getchar(); a1[i] = (c & 15); a2[i] = (c & 15); a3[i] = (c & 15); while ((c = Getchar()) <= '9' && c >= '0') { a1[i] = ((a1[i] * 10) + (c & 15)) % Mod1; a2[i] = ((a2[i] * 10) + (c & 15)) % Mod2; a3[i] = ((a3[i] * 10) + (c & 15)) % Mod3; } if (flag) { a1[i] = Mod1 - a1[i]; a2[i] = Mod2 - a2[i]; a3[i] = Mod3 - a3[i]; } } vector 
          
            answer; for (int i = 1; i <= m; i++) { if (isRight(a1, i, Mod1) && isRight(a2, i, Mod2) && isRight(a3, i, Mod3)) answer.push_back(i); } printf("%d\n", answer.size()); for (int i = 0; i < answer.size(); i++) write(answer[i]), putchar(10); return 0; } template 
           
             inline _TpInt read() { register int flag = 1; register char c = Getchar(); while ((c > '9' || c < '0') && c != '-') c = Getchar(); if (c == '-') flag = -1, c = Getchar(); register _TpInt init = (c & 15); while ((c = Getchar()) <= '9' && c >= '0') init = (init << 3) + (init << 1) + (c & 15); return init * flag; } template 
            
              inline void write(_TpInt x) { if (x < 0) { putchar('-'); write<_TpInt>(~x + 1); } else { if (x > 9) write<_TpInt>(x / 10); putchar(x % 10 + '0'); } }}int main(){ hkxadpall::main(); return 0;}