hiho一下 第144周(机会渺茫)解题报告及拓展
2024-03-26 03:05:30
题目1 : 机会渺茫
时间限制:5000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi最近在追求一名学数学的女生小Z。小Z其实是想拒绝他的，但是找不到好的说辞，于是提出了这样的要求：对于给定的两个正整数N和M，小Hi随机选取一个N的约数N'，小Z随机选取一个M的约数M'，如果N'和M'相等，她就答应小Hi。
小Z让小Hi去编写这个随机程序，到时候她review过没有问题了就可以抽签了。但是小Hi写着写着，却越来越觉得机会渺茫。那么问题来了，小Hi能够追到小Z的几率是多少呢？
输入
每个输入文件仅包含单组测试数据。
每组测试数据的第一行为两个正整数N和M，意义如前文所述。
对于40%的数据，满足1<=N,M<=106
对于100%的数据，满足1<=N,M<=1012
输出
对于每组测试数据，输出两个互质的正整数A和B（以A分之B表示小Hi能够追到小Z的几率）。
- 样例输入
-
3 2
- 样例输出
-
4 1
Solution:
Way1:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> long ans=,maxn,zhi[]; void Get_Zhi()
{
long i,j;
bool vis[maxn+];
for (i=;i<=maxn;i++)
vis[i]=true;
for (i=;i<=maxn;i++)
{
if (vis[i])
{
ans++;
zhi[ans]=i;
}
for (j=;j<=ans;j++)
{
if (i*zhi[j]>maxn)
break;
vis[i*zhi[j]]=false;
if (i%zhi[j]==)
break;
}
}
} int main()
{
long long n,m,a,b,temp,x,y;
long i,g;
scanf("%lld%lld",&n,&m);
if (n>m)
maxn=(long)sqrt(n);
else
maxn=(long)sqrt(m);
Get_Zhi();
if (n>m)
{
a=n;
b=m;
}
else
{
a=m;
b=n;
}
while (b)
{
temp=b;
b=a%b;
a=temp;
}
x=;
y=;
//a
if (a!=)
{
for (i=;i<=ans;i++)
if (a%zhi[i]==)
{
g=;
while (a%zhi[i]==)
{
a/=zhi[i];
g++;
}
x*=g;
if (a==)
break;
}
//a,n,m都有该质数，且系数都为1(若系数大于1，则相乘大于最大值)
if (a!=)
{
//x*2,y*4->x,y*2
y*=;
n/=a;
m/=a;
}
} //n
if (n!=)
{
for (i=;i<=ans;i++)
if (n%zhi[i]==)
{
g=;
while (n%zhi[i]==)
{
n/=zhi[i];
g++;
}
y*=g;
if (n==)
break;
}
if (n!=)
y*=;
} //m
if (m!=)
{
for (i=;i<=ans;i++)
if (m%zhi[i]==)
{
g=;
while (m%zhi[i]==)
{
m/=zhi[i];
g++;
}
y*=g;
if (m==)
break;
}
if (m!=)
y*=;
} a=y;
b=x;
while (b)
{
temp=b;
b=a%b;
a=temp;
}
x/=a;
y/=a;
printf("%lld %lld\n",y,x);
return ;
}
Way2:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> long ans=,maxn,zhi[]; //打质数表！ void Get_Zhi()
{
long i,j;
bool vis[maxn+];
for (i=;i<=maxn;i++)
vis[i]=true;
for (i=;i<=maxn;i++)
{
if (vis[i])
{
ans++;
zhi[ans]=i;
}
for (j=;j<=ans;j++)
{
if (i*zhi[j]>maxn)
break;
vis[i*zhi[j]]=false;
if (i%zhi[j]==)
break;
}
}
} int main()
{
long long n,m,y=;
long i,j,g1=,g2=,p[],q[],u[],v[];
scanf("%lld%lld",&n,&m);
if (n>m)
maxn=(long)sqrt(n);
else
maxn=(long)sqrt(m);
Get_Zhi(); //n
if (n!=)
{
for (i=;i<=ans;i++)
if (n%zhi[i]==)
{
g1++;
p[g1]=i;
q[g1]=;
while (n%zhi[i]==)
{
n=n/zhi[i];
q[g1]++;
}
if (n==)
break;
}
}
if (n!=)
y*=; //m
if (m!=)
{
for (i=;i<=ans;i++)
if (m%zhi[i]==)
{
g2++;
u[g2]=i;
v[g2]=;
while (m%zhi[i]==)
{
m/=zhi[i];
v[g2]++;
}
if (m==)
break;
}
}
if (m!= && m!=n)
y*=;
i=;
j=;
while (i<=g1 && j<=g2)
{
if (p[i]<u[j])
{
y*=q[i];
i++;
}
else if (u[j]<p[i])
{
y*=v[j];
j++;
}
else
{
if (q[i]>v[j])
y*=q[i];
else
y*=v[j];
i++;
j++;
}
}
while (i<=g1)
{
y*=q[i];
i++;
}
while (j<=g2)
{
y*=v[j];
j++;
}
printf("%lld 1\n",y);
return ;
}
Way3:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> long ans=,maxn,zhi[]; void Get_Zhi()
{
long i,j;
bool vis[maxn+];
for (i=;i<=maxn;i++)
vis[i]=true;
for (i=;i<=maxn;i++)
{
if (vis[i])
{
ans++;
zhi[ans]=i;
}
for (j=;j<=ans;j++)
{
if (i*zhi[j]>maxn)
break;
vis[i*zhi[j]]=false;
if (i%zhi[j]==)
break;
}
}
} int main()
{
long long n,m,a,b,temp,x,y;
long g,i,r=,t,p[],q[];
scanf("%lld%lld",&n,&m);
if (n>m)
maxn=(long)sqrt(n);
else
maxn=(long)sqrt(m);
Get_Zhi();
if (n>m)
{
a=n;
b=m;
}
else
{
a=m;
b=n;
}
while (b)
{
temp=b;
b=a%b;
a=temp;
}
x=;
y=; n/=a;
m/=a; //a
r=;
if (a!=)
{
for (i=;i<=ans;i++)
if (a%zhi[i]==)
{
r++;
p[r]=i;
q[r]=;
while (a%zhi[i]==)
{
a/=zhi[i];
q[r]++;
}
x*=q[r];
if (a==)
break;
}
//a,n,m都有该质数，且系数都为1(若系数大于1，则相乘大于最大值)
//x*2,y*4->x,y*2
if (a!=)
y*=;
}
p[r+]=; //n
if (n!=)
{
t=;
for (i=;i<=ans;i++)
if (n%zhi[i]==)
{
g=;
while (n%zhi[i]==)
{
n/=zhi[i];
g++;
}
//p[r+1]=1000000;
while (p[t]<i)
{
y*=q[t];
t++;
}
if (p[t]==i)
{
y*=(g+q[t]-);
t++;
}
else
y*=g;
if (n==)
break;
}
if (n!=)
y*=;
while (t<=r)
{
y*=q[t];
t++;
}
}
else
y*=x; //m
if (m!=)
{
t=;
for (i=;i<=ans;i++)
if (m%zhi[i]==)
{
g=;
while (m%zhi[i]==)
{
m/=zhi[i];
g++;
}
//p[r+1]=1000000;
while (p[t]<i)
{
y*=q[t];
t++;
}
if (p[t]==i)
{
y*=(g+q[t]-);
t++;
}
else
y*=g;
if (m==)
break;
}
if (m!=)
y*=;
while (t<=r)
{
y*=q[t];
t++;
}
}
else
y*=x; a=y;
b=x;
while (b)
{
temp=b;
b=a%b;
a=temp;
}
x/=a;
y/=a;
printf("%lld %lld\n",y,x);
return ;
}
/*
input:
16 8
output:
5 1 input:
60 48
output:
20 1
*/
Advance:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define maxn 100000
#define maxs 100000 long zhi[maxn],z[maxs+][],g[maxs+][],ansz[maxs+]; void Get_Zhi()
{
long i,j,s,ans=;
long long k;
bool vis[maxn+];
for (i=;i<=maxn;i++)
vis[i]=true;
for (i=;i<=maxn;i++)
{
if (vis[i])
{
ans++;
zhi[ans]=i;
for (j=i;j<=maxs;j+=i)
{
ansz[j]++;
z[j][ansz[j]]=i;
//为了求约数总数，比正确个数多1
g[j][ansz[j]]=;
}
k=(long long)i*i;
s=;
while (k<=maxs)
{
for (j=k;j<=maxs;j+=k)
g[j][ansz[j]]++;
k=(long long)k*i;
s++;
}
}
for (j=;j<=ans;j++)
{
if (i*zhi[j]>maxn)
break;
vis[i*zhi[j]]=false;
if (i%zhi[j]==)
break;
}
}
} int main()
{
long i,j,m,n;
double result=,re;
for (i=;i<=maxs;i++)
ansz[i]=;
Get_Zhi();
for (n=;n<=maxs;n++)
for (m=;m<=maxs;m++)
{
re=1.0;
i=;
j=;
while (i<=ansz[n] && j<=ansz[m])
{
if (z[n][i]<z[m][j])
{
re/=g[n][i];
i++;
}
else if (z[n][i]>z[m][j])
{
re/=g[m][j];
j++;
}
else
{
if (g[n][i]>g[m][j])
re/=g[n][i];
else
re/=g[m][j];
i++;
j++;
}
}
while (i<=ansz[n])
{
re/=g[n][i];
i++;
}
while (j<=ansz[m])
{
re/=g[m][j];
j++;
}
result+=re;
}
printf("%lf\n",result*1.0/maxs/maxs);
return ;
}
最新文章
- Node.js文件系统、路径的操作详解
- CACTI表结构和数据被动获取
- ios 修正waring：Method override for the designated initializer of the superclass '-init' not found
- DateSort选择法、冒泡法排序
- junit4 javaee 5.0 jpa SSH 单元测试问题集锦
- jquery easyui DataGrid
- 宜昌IT软件资源汇总
- JDBC事务控制管理
- 在 PL/SQL Developer 中执行SQL文件的方法
- 【ios开发】控件细究1：UITableView
- lvm创建卷组和格式化
- git错误--ssh: Could not resolve hostname ssh.github.com: Name or service not known--解决方式
- ginput函数用法
- jstat命令详解
- css selectors tips
- Java内存泄漏简单说明
- CentOS-7.x Yum Repo Mirror
- Python 爬虫入门之爬取妹子图
- javascript将算法复杂度从O(n^2)做到O(n)
- c++ 判断数组元素是否有负数(any_of)