因子と因子の個数
1559 ワード
1.因子和を求める
例題:
Description
1つの数の因子を求めるのはとても簡単で、だから明ちゃんはとても怠け者で、区間aからbの中でどの数の因子と最大を計算して、そしてこの数と彼のすべての因子を出力したいと思っています.
Input
aとb、(0)を入力します.
Output
この数と彼の各因子(同じ場合に出力が最小)を出力し、因子は小さいから大きいまで出力します.
Sample Input
1 10
Sample Output
10 = 1 + 2 + 5
コード#コード#
#include
#define MAX 1000005
using namespace std;
int num[MAX];
int main()
{
int i,j,a,b,up;
up=MAX+5;
//
for(i=1;i<=up;i++)
{
num[i]-=i;
for(j=i;j<=up;j+=i)
{
num[j]+=i;
}
}
while(~scanf("%d%d",&a,&b))
{
int maxl=a;
for(i=a+1;i<=b;i++)
{
if(num[maxl]
2.因子個数を求める
方法:判断数、数が1でなければ、その因子数は少なくとも2つ(自身と1)ある
そしてi=2からsqrt(num)までループし、num%i=0であれば因子数+2
もちろん2つの因子数が同じなら、重くしなければなりません.
#include
#include
int solve(int x) //
{
if(x==1) return 1;
int up=sqrt(x),count=2;
for(int i=2;i<=up;i++)
{
if(x%i==0)
{
if(i==up&&x/i==i) // , +1
count+=1;
else
count+=2;
}
}
return count;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int temp=solve(n);
printf("%d
",temp);
}
return 0;
}
#include
#define MAX 1000005
using namespace std;
int num[MAX];
int main()
{
int i,j,a,b,up;
up=MAX+5;
//
for(i=1;i<=up;i++)
{
num[i]-=i;
for(j=i;j<=up;j+=i)
{
num[j]+=i;
}
}
while(~scanf("%d%d",&a,&b))
{
int maxl=a;
for(i=a+1;i<=b;i++)
{
if(num[maxl]
方法:判断数、数が1でなければ、その因子数は少なくとも2つ(自身と1)ある
そしてi=2からsqrt(num)までループし、num%i=0であれば因子数+2
もちろん2つの因子数が同じなら、重くしなければなりません.
#include
#include
int solve(int x) //
{
if(x==1) return 1;
int up=sqrt(x),count=2;
for(int i=2;i<=up;i++)
{
if(x%i==0)
{
if(i==up&&x/i==i) // , +1
count+=1;
else
count+=2;
}
}
return count;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int temp=solve(n);
printf("%d
",temp);
}
return 0;
}