寒假训练——第四周（素数|因数）

A - 质因数分解

A - 质因数分解

思路：

• 分解质因数板子

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 15, M = N * 2;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;
PII a;

void solve()
{
    cin >> n;
    int t;
    for (int i = 2; i <= n / i; i ++ )
        if(n % i == 0)
        {
            t = i;
            break;
        }
    cout << n / t << endl;

    return;
}

signed main()
{
    T = 1;
    //fast;cin >> T;
    //scanf("%d", &T);

    //for (cases = 1; cases <= T; cases ++ )
    while(T -- )
        solve();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

---

B - Prime Independence

B - Prime Independence

思路：

• 严格超过我的承受范围，，不会写（望大神浇浇！）

C - Division

C - Division

题意总结：

• 找到满足p%x == 0 && q % x != 0的，最大的 x。

思路：

• 分解质因数

具体实现：

• 若 p % q != 0，x(max) = p直接得到答案
• 若p % q == 0，证明 p和q分解质因数得到的质因数相同，但质因数的次数不同；
  1. 我们的目的就转化为找到集合ok中的最大值k，其中集合ok为将p的任意的一个质因数的次数变为q中的（此质因数的）次数 -1，
  2. 即、使 q % ok集合中的任意值 != 0，如此即找到答案（满足p % k == 0 && q % k != 0的数的最大值k）
• 考虑到对 p分解质因数可能会 $TLE$ ，我们只对q分解质因数，并依次枚举每个质因数
• 时间复杂度为：$O(\sqrt{q}\ast log2(p))$最大为1e6 ~ 1e7，可以过掉，完全没压力！

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 15, M = N * 2;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;
PII a;

void solve()
{
    cin >> p >> q;

    if(p % q)
    {
        cout << p << endl;
        return;
    }

    int res = 0, t;
    // n % x == 0 && m % x != 0
    for (int i = 1; i <= q / i; i ++ )
    {
        if(q % i == 0)
        {
            if(i > 1)
            {
                t = p;
                while(t % q == 0) t /= i;
                res = max(res, t);
            }
            
            t = p;
            while(t % q == 0) t /= (q / i);
            res = max(res, t);
        }
    }

    cout << res << endl;

    return;
}

signed main()
{
    T = 1;
    fast;cin >> T;
    //scanf("%d", &T);

    //for (cases = 1; cases <= T; cases ++ )
    while(T -- )
        solve();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

---

D - Half of Same

D - Half of Same

思路：

• 暴力枚举 + 分解质因数

具体实现：

• 若可以获得相同的 n/2个数字，则必定至少可以获得一组数量大于n/2的a[i]，所以得出至少n/2的相同的数可以为a[i]的某一个数
• 如此我们枚举每一个v = a[i]，对每一个大于当前相等值a[i]的a[j]分解质因数，找出a[j]集合中至少在 n/2 - same个数中出现的最大数，更新最大值，从而得到结果
• 时间复杂度为：$O(n^2\sqrt{max(a[i])})$，最多为1e6 ~ 2e6，可以过。

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 50, M = N * 2;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

map<int, int> divide_cnt;

void divide(int x)
{
    for (int i = 1; i <= x / i; i ++ )
        if(x % i == 0)
        {
            divide_cnt[i] ++;
            if(x / i != i) divide_cnt[x / i] ++;
        }
}

void solve()
{
    cin >> n;

    int a[N];
    for (int i = 0; i < n; i ++ )
        cin >> a[i];

    int res = 0;

    for (int i = 0; i < n; i ++ )
    {
        divide_cnt.clear();
        int v = a[i];
        int same = 0;
        vector<int> d;
        for (int j = 0; j < n; j ++ )
            if(a[j] == v) same ++;
            else if(a[j] > v) d.push_back(a[j] - v);

        if(same >= n / 2)
        {
            cout << -1 << endl;
            return;
        }

        for (auto it : d)
            divide(it);

        for (auto it : divide_cnt)
            if(it.y >= n / 2 - same)
                res = max(res, it.x);
    }

    cout << res << endl;

    return;
}

signed main()
{
    T = 1;
    fast;cin >> T;
    //scanf("%d", &T);

    //for (cases = 1; cases <= T; cases ++ )
    while(T -- )
        solve();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

---

E - 分解因数

E - 分解因数

思路：

• 递归 + 分解质因数

具体实现：

• divide函数为对整数x进行因数分解，分解出的因数大于等于st的方案数，如此递归求解即可
• 递归边界为：x == 1，此时返回 1

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define mkpr make_pair
#define x first
#define y second
#define int long long

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;

const int N = 50, M = N * 2;
const int YB = 8, YM = 1e8;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int T, cases;
int n, m, times;

map<int, int> divide_cnt;

int divide(int x, int st)
{
    if(x == 1) return 1;

    int res = 0;
    for (int i = st; i <= x; i ++ )
        if(x % i == 0) res += divide(x / i, i);

    return res;
}

void solve()
{
    cin >> n;

    cout << divide(n, 2) << endl;

    return;
}

signed main()
{
    T = 1;
    fast;cin >> T;
    //scanf("%d", &T);

    //for (cases = 1; cases <= T; cases ++ )
    while(T -- )
        solve();

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72