Codeforces 1295D Same GCDs(欧拉函数)

传送门

题意:给定a,m\le10^{10},若0\le x<m,求有多少个x满足gcd(a,m)==gcd(a+x,m)

题解:如果满足gcd相同则x必须为gcd(a,m)的倍数,设gcd(a,m)=d,a=ud,m=vd,则若0\le w<v,有多个w满足gcd(u+w,v)==1。因为d是最大公因数所以gcd(u,v)==1。到这里(凭借丰富的骗分经验?)就可以直接猜一波答案是phi(v)了。所以求个gcd再求个欧拉函数就完事儿。一开始欧拉函数没写好还T了一发......这次真的是自己把答案猜对的(*—*)

下面证明一下答案:

相当于要证正整数序列上每个长度为v的周期内与v互质的数的个数相等并且它们的分布是和第一个周期[1, v]是相同的。即证gcd(kx+a,x)==1\Leftrightarrow gcd(a,x)==1,然后充分性和必要性都反证一下就好了。

为什么证明了与v互质的数的分布的周期性就好?因为有了周期性后,可以把询问的区间进行平移。最后gcd(u+w,v)==10\le w<v就可以转化为gcd(x,v)==11\le x \le v

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a,m;
inline ll read() {
	ll x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
inline ll gcd(ll a,ll b) {
	return !b?a:gcd(b,a%b);
}
inline ll phi(ll x) {
	ll ret=1;
	for (register ll i=2;i*i<=x;++i)
		if (x%i==0) {
			ll cur=1;
			while (x%i==0) {
				cur*=i;
				x/=i;
			}
			ret*=(i-1)*cur/i;
		}
	if (x>1) ret*=x-1;
	return ret;
}
int main() {
	int kase=read();
	while (kase--) {
		a=read(),m=read();
		ll v=m/gcd(a,m);
		printf("%lld\n",phi(v));
	}
	return 0;
}

 

热门文章

暂无图片
编程学习 ·

FFMPEG编译ffplay

关键就是要有SDL安装SDL(失败)yum install -y SDL-devel编译SDL2(成功) https://blog.csdn.net/quantum7/article/details/104173159编译参数# export is must use export PKG_CONFIG_PATH=/usr/local/lib/pkgconfig:${PKG_CONFIG_PATH}pkg-config --modversion ffnvcodecC…
暂无图片
编程学习 ·

Linux系统中的firewalld火墙管理及优化(firewalld)

Linux系统中的firewalld火墙管理及优化(firewalld)1.firewalld 的模块化管理及存储方式(1)火墙配置目录 /etc/firewalld 火墙模块目录 /lib/firewalld (2)firewalld的一些域网络区名称 默认配置 trusted(信任) 可接受的所有网络连接 home(家庭) 用于家庭,仅接受ss…
暂无图片
编程学习 ·

粗糙的量刑模型-随机森林算法

粗糙的刑事量刑模型-随机森林算法一、效果(一)特征重要性(二)预测精度(三)结果二、大致思路(一)数据爬取(二)数据处理1、解压缩2、去重3、格式转换4、文件移动5、法条分割为匹配的数据集6、选择罪名和法定刑7、选择量刑情节8、加重构成要件的去除9、模糊匹配相应数据…
暂无图片
编程学习 ·

JDBC

JDBC(Java DataBase Connectivity) JDBC 简介 Java 数据库连接技术。即用 Java 程序操作数据库的一套接口。是独立与 特定数据库(MySQL、SQLServer) 的管理系统,也就是无论使用的是什么类型的数据库都可以用 JDBC 去连接。 让 JDBC 去翻译底层数据库的各种指令,我们只需要使…
暂无图片
编程学习 ·

一文看懂Chrome浏览器工作原理

转自:https://juejin.im/post/5e182a47e51d453cee48c752本文是笔者对Mario Kosaka写的inside look at modern web browser系列文章的翻译。这里的翻译不是指直译,而是结合个人的理解将作者想表达的意思表达出来,而且会尽量补充一些相关的内容来帮助大家更好地理解。这篇文章…
暂无图片
编程学习 ·

ssm

目录User.javaUserController.javaUserDao.javaUserService.javaIUserService.javaUserMapper.xmlapplicationContext.xmldb.propertiesspring-mvc.xmlapplicationContext.xmlweb.xmlfailure.jspIndex.jspok.jsp pring 1.控制反转-》控制权的转移 2.依赖注入 DI 3.面向切面 aop…
暂无图片
编程学习 ·

Android数据绑定dataBinding的使用方法

想要使用Android数据绑定:dataBinding,大体分为6步:build.gradle中添加配置、编写bean数据类、编写Adapter适配器类、编写Adapter适配器的layout布局文件、编写java界面文件、编写java界面的layout布局文件。 本文以在Fragment中使用RecyclerView列表的界面来介绍。1.build.…
暂无图片
编程学习 ·

JavaScript-从入门到入土(五)

BOM BOM(Browser Object Model): 浏览器对象模型,是用来描述与浏览器进行交互的方法和接口 BOM下面有一个核心的对象 – window对象。 window下面的常用的事件操作: onload() 页面内容加载完成后执行这里的代码 onscroll() 浏览器的滚动条触发时触发此事件 onresize(…
暂无图片
编程学习 ·

三通道低功耗AS3933/PAN3501低频唤醒芯片125K

三通道低功耗 ASK 接收机 1 、概 述 PAN3501 是一款支持最多三个通道接收的低功耗 ASK 接收机,可用于检测 15kHz-150kHz之间的 LF 载波频率的数据信号并触发唤醒信号。支持检测可编程的 16 位或 32 位曼彻斯特唤醒模式。 …
暂无图片
编程学习 ·

【备忘】PHP读取apk安装包信息

PHP读取apk安装包信息可以获取应用名称、包名、版本信息等[已测试通过]感谢前辈贡献的代码!!直接上代码->biu~以下是底层封装:<?phpnamespace libraries\apk;use think\Exception;class ApkParser{//----------------------// 公共函数,供外部调用//---------------…
暂无图片
编程学习 ·

神经网络模型(Backbone)

转自:https://www.cnblogs.com/silence-cho/p/11620863.html神经网络模型(Backbone)自己搭建神经网络时,一般都采用已有的网络模型,在其基础上进行修改。从2012年的AlexNet出现,如今已经出现许多优秀的网络模型,如下图所示。 主要有三个发展方向:Deeper:网络层数更深,代…
暂无图片
编程学习 ·

openpyxl3.0官方文档(14)—— 雷达图

在工作表中以列或行排列的数据可以在雷达图中绘制。雷达图比较多个数据序列的总值。它实际上是面积图在x轴上的投影。 雷达图有两种类型:标准型雷达图,用线标记区域;填充型雷达图,用线填充整个区域;另一种类型marker是无效。如果需要标记,可以为相关系列设置这些标记。fr…
暂无图片
编程学习 ·

《spring boot +spring security安全框架》2020

《spring boot +spring security安全框架》 1.简单篇: |-导入pom 依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifactId> </dependency>|-配置config *配置类添加@Enable…
暂无图片
编程学习 ·

搭建UDS,一

UDS(Unified Diagnostic Services)诊断服务协议 UDS是一套建立在CAN , FLASH, EEPROM,定时器硬件驱动之上的软件框架。 那么如何从头开始搭建一套有UDS的产品呢? 首先你要把某块板子上的硬件驱动调试出来: 1.CAN 8bit 帧类型:标志帧 帧格式:数据帧 CANTX CANRX CAN…
暂无图片
编程学习 ·

什么是“新基建”?

近日,“新型基础设施建设”成为热词。那么,何为“新基建”?“新基建”缘何收到关注?“新基建”将改变什么?何为“新基建”?基础设施有“传统”与“新型”之分。传统基础设施:主要包括铁路、公路、机场、桥梁等。新型基础设施:与高新技术发展紧密相连,是发展信息化、智…
暂无图片
编程学习 ·

arcgis api 4.X 比例尺的添加

代码// 尺子样式 Possible Values:"ruler"|"line"var scaleBar = new ScaleBar({view: view,style:"ruler"});// Add widget to the bottom left corner of the viewview.ui.add(scaleBar, {position: "bottom-left"});ruler的line的
暂无图片
编程学习 ·

Linux笔记(六)*****网络配置

1 基本概念ip地址: 所有的在网络之间通信的机器都有一个唯一的ip地址, 来确定唯一的一个机器 192.168.168.1 端口: 一个端口可以确定一个唯一的程序(一个程序可能会使用多个端口)局域网:通信原理, 凡是在同一个局域网中通信的机器必须在同一个网段中 且ip地址是唯一不冲突的网…
暂无图片
编程学习 ·

Elasticsearch导出数据到csv文件

以下是个导出es数据到csv文件的简单脚本,脚本简单易懂,主要解决了中文乱码问题。from elasticsearch import Elasticsearch import csv import sys import json import codecsreload(sys) sys.setdefaultencoding(utf-8) # es地址:本机 localhost:9200, 远程地址 https://y…