NYOJ 478 月老的烦恼（1）

￡神魔★判官ぃ 2022-09-19 08:10 133阅读 0赞

## 月老的烦恼（1） ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 3

描述

月老最近遇到了一个很棘手的问题，就是“剩男”“剩女”急速增长，而自己这边又人手不足导致天天都得加班。现在需要你来帮助月老解决这个问题，牵红绳的规则很简单：每个男生都一个编号n（1<=n<=500000）,编号n的因数之和就是要牵线的女生的编号。

如20的因子是：1,2,4,5,10；

输入

输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).

输出

对于每组测试数据,请输出一个代表输入编号N男生的另一半的编号.

样例输入

3
    2
    10
    12

样例输出

1
    8
    16

常规方法：

#include<stdio.h>
    
    int main()
    {
    	int m,n;
    	scanf("%d",&m);
    	while(m--)
    	{
    		int i;
    		int sum = 1;
    		scanf("%d",&n);
    		for (i=2; i*i< n; ++i)
    		{
    			if (n%i == 0)
    			{
    				sum += i + n/i;
    			}
    		}
    		if (i*i == n)
    		{
    			sum += i;
    		}
    		printf("%d\n",sum);
    	}
    }

很可惜，这个方法会超时。那就打表吧，开辟一个数组，把500000以内的数的因子和保存在数组里面，直接调用即可。

#include <stdio.h>
    int main() 
    { 
    	int a[500001]={0},i,j; 
    	for( i=1; i<500001; i++) 
    	{ 
    		for( j=1; i*j<500001; j++) 
    		{ 
    			a[i*j]+=i; 
    		} 
    	}
    	scanf("%d",&i);
    	while(i--) 
    	{ 
    		scanf("%d",&j);
    		printf("%d\n",a[j]-j);
    	} 
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 NYOJ 453 小珂的烦恼

小珂的烦恼时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述小珂遇到了一个麻烦的问题，有这样的N对数（1，2），（3，5），（4，7

梦里梦外;/ 2022年09月19日 08:16/ 0 赞/ 192 阅读

相关 NYOJ 478 月老的烦恼（1）

月老的烦恼（1）时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述月老最近遇到了一个很棘手的问题，就是“剩男”“剩女”急速增长，而自

￡神魔★判官ぃ/ 2022年09月19日 08:10/ 0 赞/ 134 阅读

相关 NYOJ 275 队花的烦恼一

队花的烦恼一时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述 ACM队的队花C小+经常抱怨：“C语言中的格式输出中有十六、十、八进制

谁借莪１个温暖的怀抱￠/ 2022年09月19日 05:27/ 0 赞/ 134 阅读

相关 NYOJ 223 小明的烦恼

小明的烦恼时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述小明最近接到了一个棘手的任务，他们公司有一个电话簿.但是这是一个奇怪的电

太过爱你忘了你带给我的痛/ 2022年09月19日 05:16/ 0 赞/ 166 阅读

相关 NYOJ 100 1的个数

1的个数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述小南刚学了二进制，他想知道一个数的二进制表示中有多少个1，你能帮他写一个程

港控/mmm°/ 2022年09月19日 04:18/ 0 赞/ 161 阅读

相关 NYOJ-初学者的烦恼

初学者的烦恼时间限制： 1000 ms | 内存限制： 65535 KB 难度： 1 描述小c才开始学习c语言，让他最烦恼的就是对字符数组的操作。小C的好朋友

灰太狼/ 2022年08月25日 05:28/ 0 赞/ 208 阅读

相关 NYOJ 189 兔子的烦恼(一）

兔子的烦恼(一）时间限制： 1000 ms | 内存限制： 65535 KB 难度： 2 描述在一座山上有n个山洞（每个洞从0~n-1分别编号），这山上有一只兔

清疚/ 2022年08月25日 02:09/ 0 赞/ 124 阅读

相关队花的烦恼一(nyoj275)

队花的烦恼一时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述 ACM队的队花C小+经常抱怨：“C语言中的格式输出中有十六、十、八

约定不等于承诺〃/ 2022年08月08日 12:52/ 0 赞/ 135 阅读

相关 1的个数(nyoj100)

1的个数时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述小南刚学了二进制，他想知道一个数的二进制表示中有多少个1，你能帮他写一

偏执的太偏执、/ 2022年08月08日 12:51/ 0 赞/ 155 阅读

相关二分图匹配算法之匈牙利算法模板 hdoj1083 nyoj月老的难题

匈牙利算法是解决二分匹配的一个经典算法，昨天学长很详细的讲了一下。也算小有理解，在这里分享一下。匈牙利算法就是解决二分最优匹配的算法，比如给出hdoj上面这道题为例：[ht

阳光穿透心脏的1/2处/ 2022年03月14日 12:18/ 0 赞/ 133 阅读