平台营销型网站谈谈你对网络营销的认识

18900 小弟弟的算数题

时间限制:2000MS 代码长度限制:10KB
提交次数:37 通过次数:2

题型: 编程题 语言: G++;GCC

Description

Fczzz和大只佬是好朋友，大只佬有一个可爱的弟弟（以下简称为小弟弟）>，作为计算机专业的学生，大只佬经常写程序自动生成算术题给小弟弟做。

最近小弟弟学到了一些很神奇的运算并且讲给了大只佬听：

2*5=10

25*4=100

125*8=1000等等

小弟弟说这些数字相乘以后后面全部都是0，很神奇，并让大只佬出一些这种类型的题目给他做。大只佬想了一想，决定提高一点点算术题的难度，他编写了一段程序并且生成了n个小数。

大只佬决定每天从这n个小数里面选出2个小数，让小弟弟进行相乘的运算，因为要让小弟弟体验到神奇，当这两个小数进行相乘以后，小数点以后的部分必须全部为0。

例如 (0.25) * (4.0)=1.00000000······(小数点后全为0） 这是神奇的运算 , 但 (0.25)*(0.4)=0.1······(小数点后不全为0)这是不神奇的运算。

因为大只佬身兼数职，他不想每天都重新生成小数，他想知道生成的n个小数可以给小弟弟出多少天的题（每天出一题），于是他找来了Fczzz帮忙计算一下。

为了简化问题，Fczzz决定把问题简单化为：

生成了n个小数，为 X1,X2,X3,······，Xn. 求能选出多少组【i,j】满足：

1、1≤i≤n,1≤j≤n;

2、i小于j 并且 Xi*Xj满足上面定义的神奇的运算;

输入格式

第一行输入一个正整数n，表示生成的n个小数。 (2≤n≤200000)

接下n行，每行输入一个小数。

对于每个Xi(1≤i≤n):

1、Xi大于0并且Xi小于10000

2、小数点后最多有9位数字;

输出格式

输出一行整数，表示可以给小弟弟出多少天题。

请思考清楚时间复杂度以及浮点数的精度问题！！！

请思考清楚时间复杂度以及浮点数的精度问题！！！

请思考清楚时间复杂度以及浮点数的精度问题！！！

请注意计算过程溢出
请思考：25=10 254=100 125*8=1000

输入样例

5

0.25

4.00000000
6.000000

0.40

0.12500

输出样例

2

提示

i=1,j=2时满足神奇运算：0.25*4.00000000=1.0000000000

i=2,j=3时满足神奇运算：4.00000000*6.000000=24.00000000000000

最终代码在末尾

(不排除这不是最优解的可能)

这是我写的第一篇题解，可能写的不好。

题意

输出有多少对数满足两数相乘之后不存在小数(小数点后都是0)

需要亿点一点数学知识和前缀和知识

注意浮点数的精度问题？为什么会有精度问题？

$0<a_i<10000$，加上小数点后的9位数，我们用double类型来存小数时double可以精确这14位数。

但是如果我们将两个数字相乘会发生什么，我们就需要28位数的精度($0.001953125\times 512.000000001$)，显然double甚至long double对此也无能为力。 要想避免精度问题，可以将这些数字乘上$10^9$然后再存进一个long long的数组中。

另外，为了避免浮点数读入带来的精度误差，下面代码采用字符串读入。

long long to(string& s)     //传引用避免复制
{long long res = 0;     //最终返回的值int i = 0;while(i<s.size() && s[i]!='.'){     //小数点前的数字加到res中res*=10;res+=s[i]-'0';i++;}if(i==s.size()){  //如果输入的数字没有小数点 乘1e9再返回(因为我们需要的是转化为整数的数字)res = res*mod9;return res;}i++;        //跳过小数点int cnt=0;  //计算有多少位小数while(i<s.size()){      //小数点后的数字也加到res中res*=10;res+=s[i]-'0';i++;cnt++;}while(cnt<9){           //res后面补0 使得res和原来刚好扩大1e9res*=10;cnt++;}return res;
}

现在回到题目，将小数转换为long long之后怎么判断这两个数相乘没有小数？根据乘法
$2.500000000\times 4.000000000=1.00000000000000000$ 小数点后18个0，17个为原有的，还有一个是 $2.5\times 4=10$ 产生的。将这个应用到整数中，可以得出 $(a_i\times a_j)\%10^{18}==0$即为满足题意的一对数。

那么，问题又来了，转化为long long 之后 $0<a_i<10^{13}$ 两个数相乘肯定会爆long long。这时就要使用数学知识了！

先思考什么样的$x$才能满足$x\%10^{18}==0$ 那 $x$肯定要是$10^{18}$的倍数$x=k\times 10^{18}$，对x进行分解得到$x=k\times 2^{18}\times 5^{18}$，那怎样的两个数相乘才能有这样的结果？

设有两个数$a,b$，$a=2^{p_1}\times 5^{p_2}\times k_1，b=2^{q_1}\times 5^{q_2}\times k_1$

$(a\times b)\%10^{18}=0$，即$p_1+q_1\ge 18，p_2+q_2\ge 18$

通过上面的数学推导可以发现，我们只关心一个数字2和5的因子个数,所以可以用pair<int,int> 分别存2和5的因子数量

这样就可以写出下面$O(n^2)$的程序

#include<iostream>
#include<string>
#include<cstring>
#define ll long long
#define fr first        //宏定义简化代码
#define se second
using namespace std;
typedef pair<int,int> pii;      //pii在这
const ll mod9 = 1e9;
pii a[500005];
int n;
string s;
long long to(string& s)     //传引用避免复制
{long long res = 0;     //最终返回的值int i = 0;while(i<s.size() && s[i]!='.'){     //小数点前的数字加到res中res*=10;res+=s[i]-'0';i++;}if(i==s.size()){  //如果输入的数字没有小数点 乘1e9再返回(因为我们需要的是转化为整数的数字)res = res*mod9;return res;}i++;        //跳过小数点int cnt=0;  //计算有多少位小数while(i<s.size()){      //小数点后的数字也加到res中res*=10;res+=s[i]-'0';i++;cnt++;}while(cnt<9){           //res后面补0 使得res和原来刚好扩大1e9res*=10;cnt++;}return res;
}
int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);long long t2;cin >> n;for(int i = 1; i <= n; i++){cin >> s;           //double精度不够t2 = to(s);         //将字符串转化为乘10^9后的数字a[i] = make_pair(0,0);      //初始化while(t2>0&&t2%2==0){       //统计t2中2的个数a[i].fr++;t2/=2;}while(t2>0&&t2%5==0){       //统计t2中5的个数a[i].se++;t2/=5;}}//枚举每一对数long long ans = 0;      //存答案for(int i = 1; i <= n; i++){        for(int j = i+1; j <= n; j++){  //j从i+1开始枚举，避免重复枚举if(a[i].fr+a[j].fr>=18 && a[i].se+a[j].se>=18)  //原来两个整数数相乘后2和5的因子个数ans++;}}cout << ans;return 0;
}

兴奋的提交一波，超时！

再看一眼n的范围200000！！！

看来需要想办法优化一下最后统计答案的二重循环
将$a[i].fr+a[j].fr\ge 18$移一下项得到$a[i].fr\ge 18-a[j].fr$，也就是说对于一个$a[j]$我们所有满足上面不等式的$i$都对答案有贡献，这就自然而然的想到前缀和，很可惜，这里需要用二维前缀和。

将$a[i]$抽象成二维平面的点，因为需要用前缀和，而$a[i]$的x,y最小值可以是0，所以这里将$a[i].fr$和$a[i].se$都先加一再进行描点，用数组$q[x][y]$来表示$(0,0)-(x,y)$(左下角和右上角)的点的数量，再由前缀和公式可以得到矩形区域$(a,b)-(c,d)$点的数量为$q[c][d]-q[a-1][d]-q[c][b-1]+q[a-1][b-1]$

因为转化为long long的数字最大为$10^{13}$

${\log }_{2}10^{13}\le 44$，即前缀和数组开$45\times 45$就行了，下面代码开了$55\times 55$

如此一来，我们就可以将时间复杂度优化为$O(n+46\ast 46)$了！

这题的前缀和还有一些实现的细节在代码中展示

#include<iostream>
#include<string>
#include<cstring>
#define ac return 0;
#define ll long long
#define fr first        //宏定义简化代码
#define se second
using namespace std;
typedef pair<int,int> pii;      //pii在这
const ll mod9 = 1e9;
pii a[200005];
int n;
int mp[47][47];     //描点 用于计算前缀和
int q[47][47];      //前缀和数组
string s;
ll to(string& s)
{ll res = 0;     //最终返回的值int i = 0;while(i<s.size() && s[i]!='.'){     //小数点前的数字加到res中res*=10;res+=s[i]-'0';i++;}if(i==s.size()){        //如果输入的数字没有小数点 乘1e9再返回(因为我们需要的是转化为整数的数字)res = res*mod9;return res;}i++;        //跳过小数点int cnt=0;  //计算有多少位小数while(i<s.size()){      //小数点后的数字也加到res中res*=10;res+=s[i]-'0';i++;cnt++;}while(cnt<9){           //res后面补0 使得res和原来刚好扩大1e9res*=10;cnt++;}return res;
}
int main()
{ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);ll t2;cin >> n;for(int i = 1; i <= n; i++){cin >> s;           //double精度不够t2 = to(s);         //将字符串转化为乘10^9后的数字a[i] = make_pair(0,0);      //初始化while(t2>0&&t2%2==0){       //统计t2中2的个数a[i].fr++;t2/=2;}while(t2>0&&t2%5==0){       //统计t2中5的个数a[i].se++;t2/=5;}}memset(mp,0,sizeof(mp));    //初始化memset(q,0,sizeof(q));for(int i = 1; i <= n; i++){        //描点mp[a[i].fr+1][a[i].se+1]++;     //先将点加一}for(int i = 1; i <= 46; i++)for(int j = 1; j <= 46; j++){q[i][j] = q[i-1][j] + q[i][j-1] - q[i-1][j-1] + mp[i][j];   //前缀和公式}ll ans=0;for(int i = 1; i <= n; i++){int x = 18-a[i].fr, y = 18-a[i].se;     //算出矩形的坐下角坐标  右上角坐标为最大值46//不要忘记a[i]是加了1的所有查询区间的时候是查询[x+1,46][y+1,46]ll t = q[46][46] - q[46][y] - q[x][46] + q[x][y];if(a[i].fr>=x&&a[i].se>=y)t--;      //如果这个if满足，意味着t个点中包含了自身，需要t--ans += t;}//同一对数会数两遍，输出时要/2cout << ans/2;ac
}