GCD nyoj 1007 (欧拉函数+欧几里得)

时间:2021-09-19 09:46:23

GCD  nyoj 1007 (欧拉函数+欧几里得)

GCD

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
 
描述
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,please answer sum of  X satisfies 1<=X<=N and (X,N)>=M.
 
输入
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 (1<=N<=10^9, 1<=M<=10^9), representing a test case.
输出
Output the answer mod 1000000007
样例输入
3
1 1
10 2
10000 72
样例输出
1
35
1305000 题意:1<= x <= n ,求gcd(x,n) >= m 说有满足条件的x的和 (最后要模Mod=1000000007)
分析:
如果是求满足条件的x的个数:
因为x要满足1<=x<=n 且gcd(x,n)>=m,所以x为n的因子,即gcd(x,n)=x>=m,设y=n/x,
则y的欧拉函数为小于y且与y互质的数的个数。假设与y互质的数为p1,p2,p3……,那么gcd(x*pi,n)=x>=m.
即要找出所有符合要求的y的欧拉函数值的和即可。 因为1<= x <= n 若gcd(x,n) = x >= m 推出x是n的因子 y = n/x 与y互质且小于y的数pi 总共有eular(y)个
gcd(x*pi,n) = x >= m 所以此时满足条件的x的个数有eular(y)个
又因为 gcd(a,n) = gcd(n-a,n) 【定理记住】 所以此条件下x的和sum = n*eular(y)/2
最后再依此求出n的所有因子 计算sum相加即可 计算x的总和:附上代码
/*
author:谦智
HDU 2588-GCD(欧拉函数) 数论
*/
#include<iostream>
using namespace std;
const int Mod = ;
#define LL long long
LL eular(LL n) ;
LL eularSum(LL k) {
if (k == ) return ;//特殊值
return k*eular(k)/;
}
int main() {
int t;
cin >> t;
while (t--) {
LL n, m;
cin >> n >> m;
LL sum = ;
if (n == && m == ) {//特殊情况
cout << << endl;
continue;
}
for (LL i = ; i*i <= n; i++) {
if (n%i == ) {
if (i >= m) {
sum = (sum + n*eular(n/i)/)%Mod; //==》 sum = (sum + i*(n/i)*eular(n/i)/2)%Mod
// sum = (sum + i*eularSum(n/i))%Mod;//总共有 eular(n/i)个x使得gcd(x,n) >= m
}
if (n/i >= m && i*i != n) {
      //只需要在这里加一个i== 1的情况上面不要加 不然会重复
if (i == ) sum = (sum + n)%Mod;//当eular(i) < 2时只需要加上此时唯一满足条件的x即可 其他的eular(i)一定都是偶数因为gcd(a,n)= gcd(n-a,n)
else sum = (sum + n*eular(i)/)%Mod;
// sum = (sum + n/i*eularSum(i))%Mod;
}
}
}
cout << sum << endl;
}
}
LL eular(LL n) {
LL ans = n;
for (LL i = ; i*i <= n; i++) {
if (n%i == ) {
ans = ans/i*(i-);
while (n%i == ) {
n /= i;
}
}
}
if (n != ) ans = ans/n*(n-);
return ans;
}

 

计算x的个数:附上代码

//计算 x小于n 且gcd(x,n) >= m 的x的个数
#include<iostream>
using namespace std;
int eular(int n) ;
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
int sum = ;
for (int i = ; i*i <= n; i++) {
if (n%i == ) {
if (i >= m) {
sum += eular(n/i);
} else if (n/i >= m && i*i != n) {
sum += eular(i);
}
}
}
cout << sum << endl;
}
}
int eular(int n) {
int ans = n;
for (int i = ; i*i <= n; i++) {
if (n%i == ) {
ans = ans/i*(i-);
}
while (n%i == ) {
n /= i;
}
}
if (n != ) ans = ans/n*(n-);
return ans;
}
 

 

GCD nyoj 1007 (欧拉函数+欧几里得)的更多相关文章

  1. 【luogu3768】简单的数学题 欧拉函数&lpar;欧拉反演&rpar;&plus;杜教筛

    题目描述 给出 $n$ 和 $p$ ,求 $(\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j))\mod p$ . $n\le 10^{10}$ . ...

  2. 【poj2478-Farey Sequence】递推求欧拉函数-欧拉函数的几个性质和推论

    http://poj.org/problem?id=2478 题意:给定一个数x,求<=x的数的欧拉函数值的和.(x<=10^6) 题解:数据范围比较大,像poj1248一样的做法是不可行 ...

  3. hdoj 1286 找新朋友【欧拉函数】

    找新朋友 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submis ...

  4. HDU 3501【欧拉函数拓展】

    欧拉函数 欧拉函数是指:对于一个正整数n,小于n且和n互质的正整数(包括1)的个数,记作φ(n) . 通式:φ(x)=x*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)-..(1- ...

  5. 线段树&plus;欧拉函数——cf1114F

    调了半天,写线段树老是写炸 /* 两个操作 1.区间乘法 2.区间乘积询问欧拉函数 欧拉函数计算公式 phi(mul(ai))=mul(ai) * (p1-1)/p1 * (p2-1)/p2 * .. ...

  6. nyoj 1007 GCD&lpar;数学题 欧拉函数的应用&rpar;

    GCD 描述 The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b) ...

  7. hdu2588 GCD (欧拉函数)

    GCD 题意:输入N,M(2<=N<=1000000000, 1<=M<=N), 设1<=X<=N,求使gcd(X,N)>=M的X的个数.  (文末有题) 知 ...

  8. BZOJ 2818&colon; Gcd &lbrack;欧拉函数 质数 线性筛&rsqb;【学习笔记】

    2818: Gcd Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 4436  Solved: 1957[Submit][Status][Discuss ...

  9. poj3696 快速幂的优化&plus;欧拉函数&plus;gcd的优化&plus;互质

    这题满满的黑科技orz 题意:给出L,要求求出最小的全部由8组成的数(eg: 8,88,888,8888,88888,.......),且这个数是L的倍数 sol:全部由8组成的数可以这样表示:((1 ...

随机推荐

  1. 用MongoDB分析合肥餐饮业

    看了<从数据角度解析福州美食>后难免心痒,动了要分析合肥餐饮业的念头,因此特地写了Node.js爬虫爬取了合肥的大众点评数据.分析数据库我并没有采用MySQL而是用的MongoDB,是因为 ...

  2. linux 配置tomcat运行远程监控&lpar;JMX&rpar;

    在实际使用中,我们经常要监控tomcat的运行性能.需要配置相应的参数提供远程连接来监控tomcat服务器的性能.本文详细介绍如何一步一步的配置tomcat相应参数.允许远程连接监控. 工具/原料 v ...

  3. 【原创】javascript——事件思维导图

  4. 北京创客空间 BEIJING MAXPACE的小站

    北京创客空间 BEIJING MAXPACE的小站 北京市海淀区海淀大街1号中关村梦想实验室(原中关村国际数字设计中心)4层

  5. oracle相关函数

    (大写的PS:oracle存储过程测试进不去解决方案:重新编译:) TRUNC(sysdate, 'd') + 1   ////表示今天所在周的周一的年月日,如今天是2016.04.21周四,则TRU ...

  6. Git:git diff 命令详解

    工作目录 vs 暂存区 $ git diff <filename> 意义:查看文件在工作目录与暂存区的差别.如果还没 add 进暂存区,则查看文件自身修改前后的差别.也可查看和另一分支的区 ...

  7. 利用Tensorflow实现卷积神经网络模型

    首先看一下卷积神经网络模型,如下图: 卷积神经网络(CNN)由输入层.卷积层.激活函数.池化层.全连接层组成,即INPUT-CONV-RELU-POOL-FC池化层:为了减少运算量和数据维度而设置的一 ...

  8. Java数组扩展

    Java中,数组初始化后如何扩展数组? 示例 以下示例显示如何在创建新并初始化数组后扩展数组. package com.yiibai; public class ExtendingArray { pu ...

  9. 【python基础】如何注释代码块

    前言 编写python程序有时候需要对代码块进行comment,本文对此介绍. 方法 python注释的三种方法: 1.井号注释单行代码: # 2.三个单引号或三个双引号注释语句块: ''' 或者&q ...

  10. Hadoop2的Yarn和MapReduce2相关

    转自: http://www.aboutyun.com/thread-7678-1-1.html..   问题导读: 1.什么是yarn? 2.Yarn 和MapReduce相比,它有什么特殊作用 ? ...