历届试题矩阵翻硬币大数开方-白红宇

历届试题矩阵翻硬币大数开方

阅读量：5102 次

发布时间：2019-06-13

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

题目链接：

思路：假定一个硬币初始时是正面，它被翻转偶数次仍然是正面，翻转奇数次就是反面。考虑位于坐标(x, y)的隐蔽，设a是x的约数，b是y的约数，那么翻转坐标为(a, b)的硬币时，（x，y）也会翻转，我们只关心（x，y）翻转次数的奇偶性。那么（x，y）的翻转次数就是x的约数个数 * y的约数个数，题目要求计算反面的数量，那么就只考虑奇数次翻转，只有当x的约数个数是奇数并且y的约数个数是奇数时它们的乘积才是奇数。

那么哪些数的约数个数是奇数个？

4:1,2,4

5:1,5

6:1,2,3,6

9:1,3,9

16:1,2,4,8,16

不难发现只有平方数的约数个数是奇数，那么对于n*m的矩阵，只要计算出其中坐标（x，y）满足x是平方数，y也是平方数的数量就是答案。行下标是平方数的有sqrt(n)个，列下标是平方数的有sqrt(n)个，那么ans = sqrt(n) * sqrt(m).

AC代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                using namespace std;#define eps 1e-10#define inf 0x3f3f3f3f#define PI pair
                
                  typedef long long LL;const int maxn = 1e3 + 5;struct BigInteger { vector
                 
                  s; //12345--54321 void DealZero() { //处理前导0 for(int i = s.size() - 1; i > 0; --i){ if(s[i] == 0) s.pop_back(); else break; } } BigInteger operator = (long long num) { // 赋值运算符 s.clear(); vector
                  
                   tmp; do{ s.push_back(num % 10); num /= 10; }while(num); return *this; } BigInteger operator = (const string& str) { // 赋值运算符 s.clear(); for(int i = str.size() - 1; i >= 0; --i) s.push_back(str[i] - '0'); this->DealZero(); return *this; } BigInteger operator + (const BigInteger& b) const { BigInteger c; c.s.clear(); int len1 = s.size(), len2 = b.s.size(); for(int i = 0, g = 0; g > 0 || i < len1 || i < len2; ++i) { int x = g; if(i < len1) x += s[i]; if(i < len2) x += b.s[i]; c.s.push_back(x % 10); g = x / 10; } return c; } //大数减小数 BigInteger operator - (const BigInteger& b) const { BigInteger c; c.s.clear(); int len1 = s.size(), len2 = b.s.size(); for(int i = 0, g = 0; i < len1 || i < len2; ++i) { int x = g; if(i < len1) x += s[i]; g = 0; if(i < len2) x -= b.s[i]; if(x < 0) { g = -1; //借位 x += 10; } c.s.push_back(x); } c.DealZero(); return c; } BigInteger operator * (const BigInteger& b) const { BigInteger c, tmp; c.s.clear(); int len1 = s.size(), len2 = b.s.size(); for(int i = 0; i < len1; ++i) { tmp.s.clear();tmp; int num = i; while(num--) tmp.s.push_back(0); int g = 0; for(int j = 0; j < len2; ++j) { int x = s[i] * b.s[j] + g; tmp.s.push_back(x % 10); g = x / 10; } if(g > 0) tmp.s.push_back(g); c = c + tmp; } c.DealZero(); return c; } //单精度除法 BigInteger operator / (const int b) const { BigInteger c, tmp; c.s.clear(); int len = s.size(); int div = 0; for(int i = len - 1; i >= 0; --i) { div = div * 10 + s[i]; while(div < b && i > 0) { div = div * 10 + s[--i]; } tmp.s.push_back(div / b); div %= b; } for(int i = tmp.s.size() - 1; i >= 0; --i) c.s.push_back(tmp.s[i]); c.DealZero(); return c; } bool operator < (const BigInteger& b) const { int len1 = s.size(), len2 = b.s.size(); if(len1 != len2) return len1 < len2; for(int i = len1 - 1; i >= 0; --i) { if(s[i] != b.s[i]) return s[i] < b.s[i]; } return false; //相等 } bool operator <= (const BigInteger& b) const { return !(b < *this); } string ToStr() { string ans; ans.clear(); for(int i = s.size()-1; i >= 0; --i) ans.push_back(s[i] + '0'); return ans; } //大数开方 /**大数开方用法说明： 字符串必须从第二个位置开始输入,且s[0] = '0' scanf("%s", s+1); */ BigInteger SQRT(char *s) { string p = ""; s[0]='0'; if(strlen(s)%2 == 1) work(p, 2, s+1, 0); else work(p, 2, s, 0); BigInteger c; c.s.clear(); c = p; return c; } //开方准备 //------------------------------------ int l; int work(string &p, int o,char *O,int I){ char c, *D=O ; if(o>0) { for(l=0;D[l];D[l++]-=10) { D[l++]-=120; D[l]-=110; while(!work(p, 0, O, l)) D[l]+=20; p += (char)((D[l]+1032)/20); } } else { c=o+(D[I]+82)%10-(I>l/2)*(D[I-l+I]+72)/10-9; D[I]+=I<0 ? 0 : !(o=work(p, c/10,O,I-1))*((c+999)%10-(D[I]+92)%10); } return o; }//-----------------------------------------};ostream& operator << (ostream &out, const BigInteger& x) { for(int i = x.s.size() - 1; i >= 0; --i) out << x.s[i]; return out;}istream& operator >> (istream &in, BigInteger& x) { string s; if(!(in >> s)) return in; x = s; return in;}int main() { BigInteger a, b; char s[maxn]; scanf("%s", s+1); a = a.SQRT(s); scanf("%s", s+1); b = b.SQRT(s); cout << a * b << "\n"; return 0;}

如有不当之处欢迎指出！

转载于:https://www.cnblogs.com/flyawayl/p/8305407.html

你可能感兴趣的文章