算法 哈希
题目描述是将Ai 和 Aj 拼解成一个新的整数是k的倍数
先分析时间复杂度因为n 的范围式 [0,1e5] 所有能通过的时间复杂度是o(log(n)) o(n)
考虑的算法有哈希o(1) 双指针 二分
分析问题
把Aj 拼接到 Ai 后面 他的表达式可以转化为
Ai+10^(len)+Aj 其中==len== 表示的是后面aj的位数
那么问题就转为l 这个问题就是
这里表示方便我们使用 a来表式 Ai b来表示 10^(len)+Aj
问题转化为了 求 (a+b)%k==0 求个数的求解
猜想他的形式有点类似是 a+b=c 如果c%k==0 那么就可以 答案++ 枚举 b 找a 的个数
对于这个公式 我们可能会想到的算法可能就是 哈希
因为上面猜想是加法 所有 我们要把答案 搞成 加法
答案 满足 (a+b)%k=0;
尝试公式 是否可以这样变型呢 a%k+b%k=k
这个公式是比较 容易想到 的 例子 15 6 15%7=1 6%7=6 1+6=7;
我们只是尝试公式 并没有证明 当然 先要证明我们可以通过 程序帮我们证明是否正确
证明如下
这里 列举的例子是 p=19;
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
int p=19;
for(int i=1;i<=1000;i++){
for(int j=1000;j>=1;j--){
if((j+i)%p==0){
if(j%p+i%p==p) printf("");
else printf("%d %d\n",i,j);
}
}
}
}
通过这个程序我们发现我们答案是错误的
错误数据如下 : 这里我就不发图片了
19 988
19 967
19 950
ovo 1. 我们发现猜想错了: 观察数据 我们发现 错误的数据 全部是 19 的倍数 那也就是 猜想是错的 0+0 还是0
- 当然观察数据我们发现 错误的数据就只有 是k 的倍数 也就是如果不是k的倍数 答案是满足 那我们可以特殊判断一下也可以解出这个题
为了方便表示我们把c 是a 的余数 d是b的余数 公式当c 和d不是0的时候
c+d=k 好了我们已经转化成了一个加法问题 只要枚举 c 查一下d 就可以找到答案了
关于查d 的操作可以看一下y 总的代码
具体代码 把代码写了注释
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n, m;
int a[N], s[11][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
for (int i = 0; i < n; i ++ )
{
LL t = a[i] % m;
for (int j = 0; j < 11; j ++ )
{
s[j][t] ++ ;
t = t * 10 % m;
}
}
LL res = 0;
for (int i = 0; i < n; i ++ )
{
LL t = a[i] % m;// 枚举当前的余数 注意在前面的证明 他的取值范围是[0,m)
//余数是可以取到0 当余数取到0 的时候 另一个余数也必须取到0
int len = to_string(a[i]).size();
res += s[len][(m - t) % m];//很多人 可能在这里有疑惑
//可能认为是余数是(m-t) 其实并不是因为在前面的证明过程中 当一个余数是0的时候另一个也必须是0
//m-t 的范围是(0,m] 余数是不能取到m 当t取到0的时候 m-t 也必须是0 才满足公式
//所以我们 只需要不影响与<0<m 的数下 只要把当m-t=m 的 时候 改成0 就是对的 所以我们可以%m
//按y总的说法 把另一个余数 映射到范围是[0,m) 所以要%m
// 查阅相关资料 发现这个式子式满足关系式 也就是同余符号
//例子 7%3=1;
//2%3=1
// (7%3)%3 =1=2%3;
LL r = t;
while (len -- ) r = r * 10 % m;
if (r == (m - t) % m) res -- ;
}
printf("%lld\n", res);
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/603174/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
Ai+10^(len)+Aj 这个不是应该是 Ai * 10^(len) + Aj,len为Aj的位数
第一次写题解 也不知道有没有解释清楚