首页 > 代码库 > 蓝桥杯T126(xjb&大数开方)

蓝桥杯T126(xjb&大数开方)

2024-09-25 02:50:02   215人阅读

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T126

 

题意：中文题诶～

 

思路：显然被翻转了奇数次的硬币为反面朝上，但是本题的数据量很大，所以O(n^2)枚举每个点肯定是不行的．．．

可以反过来想一下，对于一个坐标 (i, j)，显然其只被坐标 (x, y) 影响当且仅当 x 是 i 的因子或者 y 是 j 的因子；

用 f(x) 表示 x 的因子数目，那么坐标 (i, j) 反面朝上的充要条件为 f(i)*f(j) 为奇数，即 f(i) 为奇数并且 f(j) 为奇数；

显然当且仅当 i 为完全平方数的时候 f(i) 为奇数；那么对于 n*m 的矩阵，反面朝上的硬币数目为：

小于等于n的完全平方数的数目 * 小于等于m的完全平方数的数目，即 sqrt(n)*sqrt(m)；

注意：这里的n, m范围为1e1000，需要写个大数开方；

 

代码：

技术分享 
 1 #include<iostream>
 2 #include<string>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 const int MAXN = 1e3+10;
 7 string s1, s2; //n,m;
 8 int len1, len2; //记录开根号后大数的位数；
 9 
10 int sqrta[MAXN], sqrtb[MAXN];
11 int a[MAXN], temp[MAXN], ans[MAXN];
12 
13 int compare(int a[], int b[], int len1, int len2){
14     if(len1 > len2) return 1;
15     else if(len1 < len2) return -1;
16     for(int i=len1-1; i>=0; i--){
17         if(a[i] > b[i]) return 1;
18         else if(a[i] < b[i]) return -1;
19     }
20     return 0;
21 }
22 
23 //计算A[]*B[],返回答案长度
24 int multi(int *ans, int A[], int B[], int len1, int len2){
25     for(int i=0; i<=1000; i++) ans[i]=0;//传址数组不能用memset初始化
26     for(int i=0; i<len1; i++){
27         for(int j=0; j<len2; j++){
28             ans[i+j] += A[i]*B[j];
29         }
30     }
31     for(int i=0; i<len1+len2; i++){
32         ans[i+1] += ans[i]/10;
33         ans[i] %= 10;
34     }
35     int i;
36     for(i=len1+len2; i>=0; i--){
37         if(ans[i]) break;
38     }
39     return i+1;
40 }
41 
42 //对s开方，结果倒序存储于A数组,返回答案长度
43 int get_sqrt(int *A, string s){
44     memset(A, 0, sizeof(A));
45     memset(a, 0, sizeof(a));
46     int len1 = s.size();
47     int len2 = len1>>1;
48     if(len1 & 1) len2 += 1;
49     for(int i=0,j=s.size()-1; i<s.size(); i++,j--){//翻转
50         a[j]=s[i]-‘0‘;
51     }
52     for(int i=len2-1; i>=0; i--){//从最高位开始
53         int flag;
54         int lenMul=1;
55         memset(temp, 0, sizeof(temp));
56         while((flag=compare(temp, a, lenMul, len1))==-1){
57             A[i]++;
58             lenMul=multi(temp, A, A, len2, len2);
59         }
60         if(flag==0) break;
61         else if(flag==1) A[i]--;
62     }
63     return len2;
64 }
65 
66 int main(void){
67     memset(sqrta, 0, sizeof(sqrta));
68     memset(sqrtb, 0, sizeof(sqrtb));
69     cin >> s1 >> s2;
70     len1 = get_sqrt(sqrta, s1);
71     len2 = get_sqrt(sqrtb, s2);
72     int len = multi(ans, sqrta, sqrtb, len1, len2);
73     for(int i=len-1; i>=0; i--){
74         cout << ans[i];
75     }
76     cout << endl;
77     return 0;
78 }
View Code

 

蓝桥杯T126(xjb&大数开方)


联系
我们