热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

开发笔记:GCD(欧拉函数)

本文由编程笔记#小编为大家整理,主要介绍了GCD(欧拉函数)相关的知识,希望对你有一定的参考价值。GCDhttp://acm.hdu.edu.cn/s
本文由编程笔记#小编为大家整理,主要介绍了GCD(欧拉函数)相关的知识,希望对你有一定的参考价值。



GCD

http://acm.hdu.edu.cn/showproblem.php?pid=2588

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3782    Accepted Submission(s): 2053



Problem Description

The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.

 

 


Input

The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.

 

 


Output

For each test case,output the answer on a single line.

 

 


Sample Input


3

1 1

10 2

10000 72


 

 


Sample Output


1

6

260


 

技术图片技术图片

1 #include
2 using namespace std;
3 #define lson l,mid,rt<<1
4 #define rson mid+1,r,rt<<1|1
5 #define IT set::iterator
6 #define pb push_back
7 #define eb emplace_back
8 #define maxn 200005
9 #define eps 1e-6
10 #define PI acos(-1.0)
11 #define rep(k,i,j) for(int k=i;k12 typedef long long ll;
13 typedef pair<int,int> pii;
14 typedef pairpll;
15 typedef pairint> pli;
16 typedef pairint,string>,pii> ppp;
17 typedef unsigned long long ull;
18 const long long MOD=1000000007;
19 const double oula=0.57721566490153286060651209;
20 const int INF=0x3f3f3f3f;
21 using namespace std;
22
23
24 ll Euler(ll n){
25 ll ans=n;
26 for(ll i=2;i*i<=n;i++){
27 if(n%i==0) ans=ans/i*(i-1);
28 while(n%i==0) n/=i;
29 }
30 if(n>1) ans=ans/n*(n-1);
31 return ans;
32 }
33
34 int main(){
35 std::ios::sync_with_stdio(false);
36 int t;
37 cin>>t;
38 while(t--){
39 ll n,m;
40 cin>>n>>m;
41 ll ans=0;
42 for(int i=1;i*i<=n;i++){
43 if(n%i==0){
44 if(i>=m) ans+=Euler(n/i);
45 if(i*i!=n&&n/i>=m) ans+=Euler(i);
46 }
47 }
48 cout<endl;
49 }
50 }


View Code

 


推荐阅读
  • 本题探讨了在一个有向图中,如何根据特定规则将城市划分为若干个区域,使得每个区域内的城市之间能够相互到达,并且划分的区域数量最少。题目提供了时间限制和内存限制,要求在给定的城市和道路信息下,计算出最少需要划分的区域数量。 ... [详细]
  • 本文详细介绍了 org.apache.commons.io.IOCase 类中的 checkCompareTo() 方法,通过多个代码示例展示其在不同场景下的使用方法。 ... [详细]
  • JavaScript 基础语法指南
    本文详细介绍了 JavaScript 的基础语法,包括变量、数据类型、运算符、语句和函数等内容,旨在为初学者提供全面的入门指导。 ... [详细]
  • 对象自省自省在计算机编程领域里,是指在运行时判断一个对象的类型和能力。dir能够返回一个列表,列举了一个对象所拥有的属性和方法。my_list[ ... [详细]
  • PHP 过滤器详解
    本文深入探讨了 PHP 中的过滤器机制,包括常见的 $_SERVER 变量、filter_has_var() 函数、filter_id() 函数、filter_input() 函数及其数组形式、filter_list() 函数以及 filter_var() 和其数组形式。同时,详细介绍了各种过滤器的用途和用法。 ... [详细]
  • 本文详细介绍了 iBatis.NET 中的 Iterate 元素,它用于遍历集合并重复生成每个项目的主体内容。通过该元素,可以实现类似于 foreach 的功能,尽管 iBatis.NET 并未直接提供 foreach 标签。 ... [详细]
  • 本文详细探讨了HTML表单中GET和POST请求的区别,包括它们的工作原理、数据传输方式、安全性及适用场景。同时,通过实例展示了如何在Servlet中处理这两种请求。 ... [详细]
  • 本问题探讨了在特定条件下排列儿童队伍的方法数量。题目要求计算满足条件的队伍排列总数,并使用递推算法和大数处理技术来解决这一问题。 ... [详细]
  • 使用lambda表达式排序Collections.sort(temp,(Stringa,Stringb)-{returnb.compareTo(a);});Collections ... [详细]
  • 本文详细介绍了 Java 中的 org.apache.hadoop.registry.client.impl.zk.ZKPathDumper 类,提供了丰富的代码示例和使用指南。通过这些示例,读者可以更好地理解如何在实际项目中利用 ZKPathDumper 类进行注册表树的转储操作。 ... [详细]
  • 本文介绍如何在SQL Server中创建动态SQL存储过程,并提供详细的代码实例和解释。通过这种方式,可以更灵活地处理查询条件和参数。 ... [详细]
  • 反向投影技术主要用于在大型输入图像中定位特定的小型模板图像。通过直方图对比,它能够识别出最匹配的区域或点,从而确定模板图像在输入图像中的位置。 ... [详细]
  • 本文介绍了一个SQL Server自定义函数,用于从字符串中提取仅包含数字和小数点的子串。该函数通过循环删除非数字字符来实现,并附带创建测试表、存储过程以演示其应用。 ... [详细]
  • 基于JQuery实现的评分插件
    本文介绍了一个使用JQuery创建的交互式评分控件。当用户将鼠标悬停在星星上时,左侧的星星会变为实心,右侧保持空心,并显示对应的评分等级;移开鼠标后,所有星星恢复为空心状态。 ... [详细]
  • 本文介绍了如何利用 Spring Boot 和 Groovy 构建一个灵活且可扩展的动态计算引擎,以满足钱包应用中类似余额宝功能的推广需求。我们将探讨不同的设计方案,并最终选择最适合的技术栈来实现这一目标。 ... [详细]
author-avatar
覃思慧_419
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有