月老的煩惱（1）

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：3 描述

月老最近遇到了一個很棘手的問題，就是“剩男”“剩女”急速增長，而自己這邊又人手不足導致天天都得加班?，F在需要你來幫助月老解決這個問題，牽紅繩的規則很簡單：每個男生都一個編號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

解題思路：這道題目是要求每個因子之和，我開始看錯題了以為是質因子，后面想了想也只能夠先打表啦。。。f[i]表示i的因子之和，那么還需要每次枚舉j，f[i*j] = f[i*j]+j，i*j表示的是一個因子為j的數，那么肯定要把j加進去。。最開始以為超時，結果還是過了

AC:

#include<iostream> #include<cstdio> using namespace std;int f[500005]; int main() {f[1] = -1; f[2] = 0;for(int i = 2; i <= 500000; i++){for(int j = 2; j < 500000; j++){if(i * j > 500000) break;f[i*j] += j;}}int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n",f[n]+1);}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 478的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。