2946. 整数的质因子分解

10175102262 LarsPendragon

用python无脑循环会超时!
所以应该先筛一遍再无脑循环……(大概还存在改进空间)

from math import sqrt
T=int(input())
for I in range(T):
    n=int(input())
    count=0
    while n%2 == 0:
        n//=2
        count+=1
    if count:
        print("(2,%d)"%count, end="")
    max=int(sqrt(n))+1
    for i in range(3, max, 2):
        count=0
        while n%i==0:
            n//=i
            count+=1
        if count:
            print("(%d,%d)"%(i, count), end="")
    if n!=1:
        print("(%d,1)"%n, end="")
    print()
10175102262 LarsPendragon

最快速度是kangaroo 0.284

告白于荆州

其实不用这么麻烦,比较符合Python风格的思路应该是所有质因数生成列表1,再通过集合为中介去重然后排序保存为列表2,最后用自带的count函数得到列表2内每个元素在列表1中出现的次数

CCXXXI_

现在最符合Python风格的思路是调用collections.Counter了(我不确定两年前有没有这个东西可用


for example:

from collections import Counter as C

for t in range(int(input())):
    a, c = int(input()), C()
    for i in range(2, int(a ** 0.5) + 1):
        while a % i == 0:
            a //= i
            c[i] += 1
    if a > 1:
        c[a] += 1
    print(''.join(f'({k},{v})' for k, v in c.items()))
游族网络

太妙了,欢迎参加我们游族杯,以后也要多多支持哦

shwei
// https://acm.ecnu.edu.cn/problem/2946/
#include <iostream>

using namespace std;

void getDivides(int n) {
    for (int i = 2; i <= n / i; i ++) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                n /= i;
                s ++;
            }
            printf("(%d,%d)", i , s);
        }
    }

    if (n > 1) printf("(%d,%d)", n , 1);
    puts("");
}

int main() {
    int T;
    cin >> T;

    while (T --) {
        int n;
        cin >> n;
        getDivides(n);
    }

    return 0;
}
aiden
#include <iostream>
#include <vector>
using namespace std;

struct item
{
    int p;
    int e;
};

bool isPrime(int n)
{
    if (n % 2 == 0)
        return false;
    for (int i = 3; i * i < n; ++i)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

int main()
{
    vector<int> Prime({ 2 });
    for (int i = 3; i < 20000; ++i)
        if (isPrime(i))
            Prime.push_back(i);
    int t;
    cin >> t;
    while (t--)
    {
        int a;
        cin >> a;
        vector<item> vec;
        for (auto beg = Prime.begin(); beg != Prime.end(); beg++)
        {
            if (a % *beg == 0)
            {
                int cnt = 0;
                while (a % *beg == 0)
                {
                    ++cnt;
                    a /= *beg;
                }
                vec.push_back({ *beg,cnt });
            }
            else if (a == *beg)
            {
                vec.push_back({ a, 1 });
                break;
            }
        }
        for (const auto &i : vec)
            cout << '(' << i.p << "," << i.e << ')';
        cout << endl;
    }
    return 0;
}
Li Dao

不用筛素数哦
这里不用筛素数,因为从小到大枚举因数,如果枚举的那个因数不是素数(比如是6),那么,比那个因数的的素因数(2和3)已经把这个数“掏空”了(枚举到6的时候,N%6已经不为0了,因为N已经把2和3全部除完了)

include

using namespace std;
int T,n;

void solve()
{
int N=n;
for(int i=2;i<=n;i++) //不要像我一样从1开始枚举,囧
{
int cnt=0;
if(N%i!=0) continue;
while(N%i==0)
{
N/=i;
cnt++;
}
printf(“(%d,%d)”,i,cnt);
if(N==1) break;
}
cout<>T;
for(int step=0;step>n;
solve();
}
}

你当前正在回复 博客/题目
存在问题!