Wannafly挑战赛29 B 白井黑子 (数论+map)

2024-02-10 16:48

本文主要是介绍Wannafly挑战赛29 B 白井黑子 (数论+map),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:https://ac.nowcoder.com/acm/contest/271/B
来源:牛客网
 

kuroko 作为常盘台唯一的空间系能力者,在每年例行的能力测试中可绝对不能让 misaka 失望哦,但是由于她的等级只是 level 4「大能力者」,在能力测试中会遇到不少困难。kuroko 是一个凡事都会尽力的好女孩,所以请你帮她算出她最多能完成多少测试吧

对于空间系能力者测试的内容是检验对物体进行空间移动的能力,测验时一共有 n 个物品放在一条直线上,每个物品都有一个坐标 ai ,kuroko 可以选择两个物品并使用能力交换它们的位置,但是如果两个物品的坐标不满足 kuroko 的计算公式的话,她就没有办法使用能力。

具体来说,对于坐标 ai ,其在 kuroko 的计算公式中是用参数 f(ai) 表示的。f(ai) 是 ai 各数位相乘的结果,由于 level 4「大能力者」在学园都市中也是很强大的存在,所以满足公式的条件不会太苛刻,对于两个物品 ai, aj ,如果 f(ai) x f(aj) 不能被某个自然数的 k 次幂表示 的话,那么 kuroko 就能对这两个物品使用能力。

现在 kuroko 想知道,有多少对物品她可以对其施展能力,知道了这个后她就知道自己能完成多少测验了。

这里认为任何自然数的 0 次幂都是 1。

输入描述:

第一行两个数,n, k 。第二行共 n 个数 ai 表示这 n 个物品在直线上的坐标。

输出描述:

输出共一个数,表示 kuroko 能对其使用能力的无序物品对数。

示例1

输入

复制

6 3
113 10 11 1110 33 110

输出

复制

2

备注:

2 ≤ n ≤ 105, 0 ≤ ai, k ≤ 1018
#include<bits/stdc++.h>
using namespace std;
#define Sheryang main
const int maxn=1e5+7;
typedef long long ll;
const int mod=998244353;struct node
{int a,b,c,d;node (int _a,int _b,int _c,int _d){a=_a;b=_b;c=_c;d=_d;}
};
map<node,int>m;bool operator < (node i,node j)
{if(i.a!=j.a) return i.a<j.a;if(i.b!=j.b) return i.b<j.b;if(i.c!=j.c) return i.c<j.c;return i.d<j.d;
}ll ans,tot,k,cnt;
void solve(ll x)//因为x是各数位的乘积 所以质因子只有2 3 5 7四种 记录每一种 每次求补集即可
{node p(0,0,0,0);while(x){int t = x % 10;if(t == 0) {++ tot; return;}if(t == 2) ++ p.a;if(t == 3) ++ p.b;if(t == 4) p.a += 2;if(t == 5) ++ p.c;if(t == 6) ++ p.a, ++ p.b;if(t == 7) ++ p.d;if(t == 8) p.a += 3;if(t == 9) p.b += 2;x /= 10;}if(k){p.a %= k;p.b %= k;p.c %= k;p.d %= k;node q((k - p.a) % k, (k - p.b) % k, (k - p.c) % k, (k - p.d) % k);ans -= m[q];++ m[p];}else{if(!p.a && !p.b && !p.c && !p.d)ans-=cnt,cnt++;}
}int Sheryang()
{int n;scanf("%d %lld",&n,&k);ans=1LL*n*(n-1)/2;for(int i=1;i<=n;i++){ll x;scanf("%lld",&x);solve(x);}if(k) ans-=1LL*(n+n-tot-1)*tot/2;printf("%lld\n",ans);return 0;
}

 

这篇关于Wannafly挑战赛29 B 白井黑子 (数论+map)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/697598

相关文章

SpringBoot如何通过Map实现策略模式

《SpringBoot如何通过Map实现策略模式》策略模式是一种行为设计模式,它允许在运行时选择算法的行为,在Spring框架中,我们可以利用@Resource注解和Map集合来优雅地实现策略模式,这... 目录前言底层机制解析Spring的集合类型自动装配@Resource注解的行为实现原理使用直接使用M

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

JavaScript中的Map用法完全指南

《JavaScript中的Map用法完全指南》:本文主要介绍JavaScript中Map用法的相关资料,通过实例讲解了Map的创建、常用方法和迭代方式,还探讨了Map与对象的区别,并通过一个例子展... 目录引言1. 创建 Map2. Map 和对象的对比3. Map 的常用方法3.1 set(key, v

Golang中map缩容的实现

《Golang中map缩容的实现》本文主要介绍了Go语言中map的扩缩容机制,包括grow和hashGrow方法的处理,具有一定的参考价值,感兴趣的可以了解一下... 目录基本分析带来的隐患为什么不支持缩容基本分析在 Go 底层源码 src/runtime/map.go 中,扩缩容的处理方法是 grow

Go语言利用泛型封装常见的Map操作

《Go语言利用泛型封装常见的Map操作》Go语言在1.18版本中引入了泛型,这是Go语言发展的一个重要里程碑,它极大地增强了语言的表达能力和灵活性,本文将通过泛型实现封装常见的Map操作,感... 目录什么是泛型泛型解决了什么问题Go泛型基于泛型的常见Map操作代码合集总结什么是泛型泛型是一种编程范式,允

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》:本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添

Java中List转Map的几种具体实现方式和特点

《Java中List转Map的几种具体实现方式和特点》:本文主要介绍几种常用的List转Map的方式,包括使用for循环遍历、Java8StreamAPI、ApacheCommonsCollect... 目录前言1、使用for循环遍历:2、Java8 Stream API:3、Apache Commons

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

数论ZOJ 2562

题意:给定一个数N,求小于等于N的所有数当中,约数最多的一个数,如果存在多个这样的数,输出其中最大的一个。 分析:反素数定义:对于任何正整数x,其约数的个数记做g(x).例如g(1)=1,g(6)=4.如果某个正整数x满足:对于任意i(0<i<x),都有g(i)<g(x),则称x为反素数。 性质一:一个反素数的质因子必然是从2开始连续的质数。 性质二:p=2^t1*3^t2*5^t3*7

POJ2247数论

p = 2^a*3^b*5^c*7^d 求形如上式的第n小的数。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.u