GCD nyoj 1007 (欧拉函数+欧几里得)
GCD
- 描述
- 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 (欧拉函数+欧几里得)的更多相关文章
-
【luogu3768】简单的数学题 欧拉函数(欧拉反演)+杜教筛
题目描述 给出 $n$ 和 $p$ ,求 $(\sum\limits_{i=1}^n\sum\limits_{j=1}^nij\gcd(i,j))\mod p$ . $n\le 10^{10}$ . ...
-
【poj2478-Farey Sequence】递推求欧拉函数-欧拉函数的几个性质和推论
http://poj.org/problem?id=2478 题意:给定一个数x,求<=x的数的欧拉函数值的和.(x<=10^6) 题解:数据范围比较大,像poj1248一样的做法是不可行 ...
-
hdoj 1286 找新朋友【欧拉函数】
找新朋友 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submis ...
-
HDU 3501【欧拉函数拓展】
欧拉函数 欧拉函数是指:对于一个正整数n,小于n且和n互质的正整数(包括1)的个数,记作φ(n) . 通式:φ(x)=x*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)-..(1- ...
-
线段树+欧拉函数——cf1114F
调了半天,写线段树老是写炸 /* 两个操作 1.区间乘法 2.区间乘积询问欧拉函数 欧拉函数计算公式 phi(mul(ai))=mul(ai) * (p1-1)/p1 * (p2-1)/p2 * .. ...
-
nyoj 1007 GCD(数学题 欧拉函数的应用)
GCD 描述 The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b) ...
-
hdu2588 GCD (欧拉函数)
GCD 题意:输入N,M(2<=N<=1000000000, 1<=M<=N), 设1<=X<=N,求使gcd(X,N)>=M的X的个数. (文末有题) 知 ...
-
BZOJ 2818: Gcd [欧拉函数 质数 线性筛]【学习笔记】
2818: Gcd Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 4436 Solved: 1957[Submit][Status][Discuss ...
-
poj3696 快速幂的优化+欧拉函数+gcd的优化+互质
这题满满的黑科技orz 题意:给出L,要求求出最小的全部由8组成的数(eg: 8,88,888,8888,88888,.......),且这个数是L的倍数 sol:全部由8组成的数可以这样表示:((1 ...
随机推荐
-
用MongoDB分析合肥餐饮业
看了<从数据角度解析福州美食>后难免心痒,动了要分析合肥餐饮业的念头,因此特地写了Node.js爬虫爬取了合肥的大众点评数据.分析数据库我并没有采用MySQL而是用的MongoDB,是因为 ...
-
linux 配置tomcat运行远程监控(JMX)
在实际使用中,我们经常要监控tomcat的运行性能.需要配置相应的参数提供远程连接来监控tomcat服务器的性能.本文详细介绍如何一步一步的配置tomcat相应参数.允许远程连接监控. 工具/原料 v ...
- 【原创】javascript——事件思维导图
-
北京创客空间 BEIJING MAXPACE的小站
北京创客空间 BEIJING MAXPACE的小站 北京市海淀区海淀大街1号中关村梦想实验室(原中关村国际数字设计中心)4层
-
oracle相关函数
(大写的PS:oracle存储过程测试进不去解决方案:重新编译:) TRUNC(sysdate, 'd') + 1 ////表示今天所在周的周一的年月日,如今天是2016.04.21周四,则TRU ...
-
Git:git diff 命令详解
工作目录 vs 暂存区 $ git diff <filename> 意义:查看文件在工作目录与暂存区的差别.如果还没 add 进暂存区,则查看文件自身修改前后的差别.也可查看和另一分支的区 ...
-
利用Tensorflow实现卷积神经网络模型
首先看一下卷积神经网络模型,如下图: 卷积神经网络(CNN)由输入层.卷积层.激活函数.池化层.全连接层组成,即INPUT-CONV-RELU-POOL-FC池化层:为了减少运算量和数据维度而设置的一 ...
-
Java数组扩展
Java中,数组初始化后如何扩展数组? 示例 以下示例显示如何在创建新并初始化数组后扩展数组. package com.yiibai; public class ExtendingArray { pu ...
-
【python基础】如何注释代码块
前言 编写python程序有时候需要对代码块进行comment,本文对此介绍. 方法 python注释的三种方法: 1.井号注释单行代码: # 2.三个单引号或三个双引号注释语句块: ''' 或者&q ...
-
Hadoop2的Yarn和MapReduce2相关
转自: http://www.aboutyun.com/thread-7678-1-1.html.. 问题导读: 1.什么是yarn? 2.Yarn 和MapReduce相比,它有什么特殊作用 ? ...