题目链接:uva 11440 - Help
Tomisu
题目大意:给定n和m,求从2~n!中的数x,要求x的质因子均大于m,问说x有多少个,答案模上1e9+7。
解题思路:
(1)n!=k∗m!(n≥m)
(2)
如果有gcd(x,T)=1,那么gcd(x+T,T)=gcd(x,T)=1
题目要求说x的质因子必须要大于m,也就是说x不能包含2~m的因子,那么gcd(x,m!)=1,于是我们求出ϕ(m!),小于m!并且满足gcd(x,m!)=1的个数。
那么根据(2)可得从[m!+1, 2*m!]中的x个数也是ϕ(m!)个;因为如果存在gcd(x,T)=a,那么gcd(x+T,T)=gcd(x,T)=a.
又因为(1),所以最后n!以内的x个数为:n!∗ϕ(m!)m!
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e7;
const ll MOD = 100000007;
int np, pri[maxn+5], vis[maxn+5];
ll fact[maxn+5], phi[maxn+5];
void prime_table (ll n) {
np = 0;
for (ll i = 2; i <= n; i++) {
if (vis[i])
continue;
pri[np++] = i;
for (ll j = i * i; j <= n; j += i)
vis[j] = 1;
}
}
void gcd (ll a, ll b, ll& d, ll& x, ll& y) {
if (b == 0) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a%b, d, y, x);
y -= (a/b) * x;
}
}
inline ll inv_number (ll a, ll n) {
ll d, x, y;
gcd(a, n, d, x, y);
return (x + n) % n;
}
void init (ll n) {
fact[1] = phi[1] = 1;
for (ll i = 2; i <= n; i++) {
fact[i] = (fact[i-1] * i) % MOD;
phi[i] = phi[i-1];
if (vis[i] == 0) {
phi[i] *= ((i-1) * inv_number(i, MOD)) % MOD;
phi[i] %= MOD;
}
}
}
ll solve (int n, int m) {
ll ans = fact[n] * phi[m] % MOD;
return (ans - 1 + MOD) % MOD;
}
int main () {
prime_table(maxn);
init (maxn);
int n, m;
while (scanf("%d%d", &n, &m) == 2 && n + m) {
printf("%lld\n", solve(n, m));
}
return 0;
}
分享到:
相关推荐
算法-数论- 欧拉函数.rar
COMSOL 两相流 欧拉-欧拉 双流体模型
第八讲-机器人动力学--牛顿-欧拉方程.ppt
欧拉函数 C语言实现 #include "iostream" #include "math.h" #define maxsize 100 using namespace std; typedef struct node { int num; int total; }struct_num; struct_num a[maxsize]; int is_prime(int n)
20210225-东吴证券-长城汽车-601633-看好欧拉品牌崛起.pdf
欧拉函数是数论中很重要的一个函数,欧拉函数是指:对于一个正整数 n ,小于 n 且和 n 互质的正整数(包括 1)的个数,记作 φ(n) 。 完全余数集合: 定义小于 n 且和 n 互质的数构成的集合为 Zn ,称呼这个集合为...
matlab开发-Odshocktubeusingrichtmyermethod的欧拉方程的数值解。采用两步Richtmyer方法对SOD激波管问题的欧拉方程进行了数值求解。
东方通-入局欧拉操作系统,打开第二成长曲线.pdf
视频讲解欧拉定理和欧拉函数的证明。详细解释了证明简化剩余系的关系为什么要先证明完全剩余系的关系。以及欧拉函数的计算。
matlab开发-1采用欧拉方法的存储节点美国解决方案。[t,y]=Euler_-Modified_-ode(f,t0,y0,tend,niter)
Eulerequation-Jacobian_欧拉方程_左右特征向量_雅可比矩阵_雅可比_createcw9.zip
Eulerequation-Jacobian_欧拉方程_左右特征向量_雅可比矩阵_雅可比_createcw9_源码.rar
组合数学中经典定理 的实现 其中有: cayley定理 mobius 定理 欧拉函数 序数法 整数拆分等
计算机数组分析实验,改进的欧拉方法,用C++实现。
给出了欧拉函数的部分性质的证明
1. 熟悉求解常微分方程初值问题的有关方法和理论,主要是改进欧拉法; 2. 会编制上述方法的计算程序,包括求解微分方程组的计算程序; 3. 针对实习编制程序,并上机计算其所需要的结果; 4. 通过对各种求解方法的...
MATLAB程序分享使用欧拉Euler法求解微分方程组源程序-MATLAB使用欧拉Euler法求解微分方程组 源程序代码.rar 程序代码见附件,拿资料请顺便顶个贴~~ 如果下载有问题,请加我 qq 1530497909,给你在线传
讲义204-第二章第四讲-欧拉函数的计算(2023-1005,周四34).pdf