主题：第48次编程比赛题目
iAkiak [专家分：8460] 发布于 2007-02-09 09:40:00
第一题：
输入2个数字n,s。求数字n的所有因数之和除以s的余数。
比如输入6 5
6的因数有1,2,3,6,因数之和为12,因为12除以5的余数为2
于是输出2。
假设n,s都不超过5000000
第二题：
输入3个数字n, m, s。求数字n的m次方的所有因数之和除以m的余数。
比如输入6 2 5
6^2=36
36的因数有1,2,3,4,6,9,12,18,36,因数之和为91
91除以5的余数为1，所以输出1。
假设n, m, s都不超过5000000
接口请定义为：
int SumFactorMod(int n, int s);
int SumFactorMod(int n, int m, int s);
有问题请在次联系：
http://www.programfan.com/club/showbbs.asp?id=217779
最后更新于：2007-02-09 11:48:00
回复列表 （共26个回复）
11 楼
bloodybg [专家分：1510] 发布于 2007-02-09 15:15:00
第一题：
int SumFactorMod(int n, int s)
{
int i = 2, count;
int sum, temp;
if (1 == n)
return n % s;
sum = n + 1;
while (n != 1)
{
if (n % i == 0)
{
count = 1;
while (n % i == 0)
{
temp = (int)pow(i, count);
n /= i;
if (n < temp)
continue;
if (n == temp)
{
sum += temp;
continue;
}
sum += (temp + n);
count ++;
}
}
i ++;
}
return sum % s;
}
12 楼
wshong [专家分：1880] 发布于 2007-02-09 17:24:00
第二题，感觉写得好乱，写了好久，不过还是实现，可能还有bug！
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
long pows(int x, int n)
{
long value = 1;
for(int i = 0; i < n; i ++)
value *= x;
return value;
}
int SumFactorMod(int n, int s,int a[], int& index)
{
for(int i = 2; i <= sqrt(n); i ++){
int j = i * i;
while(j <= n ){
j += i;
if(j == n)
a[index++] = i;
}
}
return 0;
}
int SumFactorMod(int n, int m, int s)
{
int a[1000];
int b[1000];
int index = 0;
SumFactorMod(n, s, a, index);
int k = 0;
b[k ++] = 1;
for(int i = 0; i < index; i ++)
{
b[k ++] = a[i];
b[k ++] = n /a[i];
}
b[k ++] = n;
int len = k ;
int sqrt = pows(n,m/2);
int h;
for(int i = 2; i <= m; i ++)
{
for(int j = 0; j < k ;j ++)
{
int flag = 0;
for(int u = 0; u < len; u ++)
{
h = b[j] * i;
if(h > sqrt||b[u] == h)
{
flag = 1;
break;
}
}
if(flag == 1)
continue;
else {
b[len] = h;
len ++;
}
}
}
int r = pows(n,m);
int max = b[0];
int sum = 0;
int temp = 0;
for(int i = 1; i< len; i++)
if(max < b[i])
{
max = b[i];
temp = i;
}
for(int i = max +1 ; i <= sqrt;i++)
{
if(r % i == 0)
b[len++] = i;
}
if(max * max == r)
{
len --;
b[temp]=b[len];
}
for(int i = 0; i < len; i ++)
{
sum += b[i] + r / b[i];
}
if(max * max == r)
{
sum += max;
}
printf("%d\n", sum % s );
}
int main()
{
int m,n,s;
while(1)
{
scanf("%d%d%d",&n,&m,&s);
SumFactorMod(n,m,s);
}
system("pause");
return 0;
}
13 楼
bpttc [专家分：8790] 发布于 2007-02-09 19:18:00
1.第一题
//函数原型 int SumFactorMod(int n, int s);
//输入参数 n>0, s>0;
//函数功能 求数字n的所有因数之和除以s的余数
//输出值 输出值>=0时,为所求结果,
// -1 参数错误
#include <math.h>
#define ERROR -1
int SumFactorMod(int n, int s)
{
if( n<=0 || s<=0 ) return ERROR;
int i;
int sum=0;
double sq=sqrt( (double)n );
for(i=1; i<=sq; ++i)
{
if(n%i==0) sum += i + ( (i*i==n)?0:(n/i) );
}
return sum%s;
}
----------------------------------------------------------------------------
2.第二题
//函数原型 int SumFactorMod(int n, int m, int s);
//输入参数 n>0, s>0;
//函数功能 求数字n的m次方的所有因数之和除以m的余数
//输出值 输出值>=0时,为所求结果,
// -1 参数错误
#include <math.h>
#define ERROR -1
int SumFactorMod(int n, int m, int s)
{
if( n<=0 || s<=0 || m<=0 ) return ERROR;
int i;
int sum=0;
long num=pow(n,m);
double sq=sqrt( (double)num );
for(i=1; i<=sq; ++i)
{
if(num%i==0)
sum += i + ( (i*i==num)?0:(num/i) );
}
return sum%s;
}
14 楼
rj1985 [专家分：20] 发布于 2007-02-09 20:06:00
//=================================
//第一题程序
//=================================
#include<iostream.h>
#include<math.h>
long int SumFactorMod(long int ,long int);
void main()
{
long int n,s;
cout<<"Please Input 2 Number:"<<endl;
cin>>n>>s;
cout<<"Rusult="<<SumFactorMod(n,s)<<endl;
}
long int SumFactorMod(long int n,long int s)
{
int i;
long int sum=0;
for (i=1;i<=sqrt(n);i++)
if (n%i==0)
{
cout<<i<<" "<<n/i<<" ";
sum+=i;
if (i*i!=n) sum+=(n/i);
}
return (sum%s);
}
//=================================
//第二题程序
//=================================
#include<iostream.h>
#include<math.h>
long int SumFactorMod(long int,long int,long int);
void main()
{
long int n,m,s;
cout<<"Please Input 3 Number:"<<endl;
cin>>n>>m>>s;
cout<<"n="<<n<<" m="<<m<<" s="<<s<<endl;
cout<<"Rusult="<<SumFactorMod(n,m,s)<<endl;
}
long int SumFactorMod(long int n,long int m,long int s)
{
int i;
long int sum=0;
cout<<"n^m="<<n<<"^"<<m<<"=";
n=pow(n,m);
cout<<n<<endl;
for (i=1;i<=sqrt(n);i++)
if (n%i==0)
{
sum+=i;
if (i*i!=n) sum+=(n/i);
}
return (sum%s);
}
15 楼
marry3640 [专家分：0] 发布于 2007-02-09 20:11:00
；这题目太容易了，还说什么编程比赛。
#include "stdio.h"
int sumFactorMod(int ,int );
void main()
{
int n=120,s=5;
int sum=sumFactorMod( n, s);
printf("%d\n",sum);
}
int sumFactorMod(int n,int s)
{
int fact[200];
int j=1,i=0,b=0;
for(;;)
{
if(n%j==0)
{
fact[i]=j;
i++;
}
if(j==n)
break;
j++;
}
for(j=0;j<=i-1;j++)
{
b=b+fact[j];
}
return b%s;
}
16 楼
dongch007 [专家分：20] 发布于 2007-02-09 20:15:00
int SumFactorMod(int n, int s)
{
int i;
int sum=0;
for(i=1;i<=sqrt(n);i++)
{
if(n%i==0) sum+=(i+n/i);
}
i--;
if(i*i==n) sum-=i;
return sum%s;
}
int SumFactorMod(int n, int m,int s)
{
int i;
int sum=0;
for(i=1;i<m;i++)
{
n*=n;
}
for(i=1;i<=sqrt(n);i++)
{
if(n%i==0) sum+=(i+n/i);
}
i--;
if(i*i==n) sum-=i;
return sum%s;
}
瞎写的，不知道是不是这个意思，我很弱的说..
17 楼
bpttc [专家分：8790] 发布于 2007-02-09 20:49:00
//函数原型 int SumFactorMod(int n, int s);
//输入参数 n>0, s>0;
//函数功能 求数字n的所有因数之和除以s的余数
//输出值 输出值>=0时,为所求结果,
// -1 参数错误
#define ERROR -1
int SumFactorMod(int n, int s)
{
if( n<=0 || s<=0 ) return ERROR;
int i=1,j;
int sum=0;
while( i<(j=n/i) )
{
if(n%i==0) sum+=(i+j);
++i;
}
if(i==j) sum+=i;
return sum%s;
}
----------------------------------------------------------------------
//函数原型 int SumFactorMod(int n, int m, int s);
//输入参数 n>0, m>0, s>0;
//函数功能 求数字n的m次方的所有因数之和除以m的余数
//输出值 输出值>=0时,为所求结果,
// -1 参数错误
#define ERROR -1
int SumFactorMod(int n, int m, int s)
{
if( n<=0 || s<=0 || m<=0 ) return ERROR;
int i=1,j;
int sum=0;
double num=1;
for(j=0; j<m; ++j)
num*=n;
while( i<(j=num/i) )
{
if( ((int)num)%i==0 ) sum+=(i+j);
++i;
}
if(i==j) sum+=i;
return sum%s;
}
18 楼
argentmoon [专家分：13260] 发布于 2007-02-09 23:14:00
两题就写一个吧，复杂度差不了多少，麻烦楼主测试第一题的时候把m当成1测^-^
inline long long pow(long long j, int m){
long long tmp = 1;
while(m){
if(m & 1) tmp *= j;
j *= j;
m >>= 1;
}
return tmp;
}
int SumFactorMod(int n, int m, int s){
long long sum = 1;
int i = 2, limit = (int) sqrt((double)(n));
while(i <= n && i <= limit){
int ct = 0;
while(!(n % i)){
n /= i;
ct++;
}
if(ct)
sum *= ((pow(i, ct * m + 1) - 1) / (i - 1));
i++;
}
if(n > 1) sum *= ((pow(n, m + 1) - 1) / (n - 1));
return (int) (sum % s);
}
19 楼
ndam [专家分：10] 发布于 2007-02-10 09:48:00
学习
20 楼
ndam [专家分：10] 发布于 2007-02-10 09:50:00
看看
我来回复
您所在位置：