Jasper08

320

lstm_x
gyxgyxAK
Moyou
Ele
yankai
mmxx312

Jasper08
12小时前

### 题目描述

#### 样例

3
3
6
8


2
2
4


### 代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
int n;
scanf("%d", &n);
while (n --) {
int x;
scanf("%d", &x);

int euler = x;
for (int i = 2; i <= x/i; ++i) {
if (x % i == 0) {
euler = euler / i * (i-1);
while (x % i == 0)
x /= i;
}
}
if (x != 1)
euler = euler / x * (x-1);
printf("%d\n", euler);
}
return 0;
}


#include <iostream>
#include <cstdio>

using namespace std;

int gcd(int a, int b) {
if (a % b == 0)
return b;
else
return gcd(b, a%b);
}

int main() {
int n;
scanf("%d", &n);
while (n --) {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", gcd(a, b));
}
return 0;
}


#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
int n;
scanf("%d", &n);

unordered_map<int, int> prime;

while (n --) {
int x;
scanf("%d", &x);

for (int i = 2; i <= x/i; ++i) {
while (x % i == 0)
x /= i, prime[i] ++;
}
if (x > 1)
prime[x] ++;
}

ll res = 1;
for (auto i : prime) {
ll p = i.first, r = i.second;
ll t = 1;
while (r --)
t = (p * t + 1) % mod;
res = res * t % mod;
}

printf("%lld", res);

return 0;
}


### 题目描述

#### 样例

3
2
6
8


252


### 算法分析

unordered_map<int, int> prime;

while (n --) {
int x;
scanf("%d", &x);

for (int i = 2; i <= x/i; ++i) {
while (x % i == 0)
x /= i, prime[i] ++;
}
if (x > 1)
prime[x] ++;
}


1. 定义一个临时变量 $t$，储存 $\sum_{j=0}^{r_i}p_i^j$ 的结果，并将其初始化为 $1$.
2. 将 $t$ 乘上 $p_i$ 并加上 $1$，此时 $t=p_i+1$.
3. 再将 $t$ 乘上 $p_1$ 并加上 $1$，此时 $t=P-i(p_i+1)+1=p_i^2+p_i+1$.

ll res = 1;
for (auto i : prime) {
ll p = i.first, r = i.second;
ll t = 1;
while (r --)
t = (p * t + 1) % mod;
res = res * t % mod;
}


### 完整代码

#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
int n;
scanf("%d", &n);

unordered_map<int, int> prime;

while (n --) {
int x;
scanf("%d", &x);

for (int i = 2; i <= x/i; ++i) {
while (x % i == 0)
x /= i, prime[i] ++;
}
if (x > 1)
prime[x] ++;
}

ll res = 1;
for (auto i : prime) {
ll p = i.first, r = i.second;
ll t = 1;
while (r --)
t = (p * t + 1) % mod;
res = res * t % mod;
}

printf("%lld", res);

return 0;
}


#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
int n;
scanf("%d", &n);

unordered_map<int, int> prime;

while (n --) {
int x;
scanf("%d", &x);
for (int i = 2; i <= x/i; ++i) {
while (x % i == 0)
prime[i] ++, x /= i;
}
if (x > 1)
prime[x] ++;
}

ll res = 1;
for (auto i : prime)
res = res * (i.second+1) % mod;

printf("%lld", res);

return 0;
}


### 题目描述

#### 样例

3
2
6
8


12


### 算法

（详情见 867 分解质因数 题解

#include <iostream>
#include <cstdio>
#include <unordered_map> //用哈希表存储质数

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
int n;
scanf("%d", &n);

unordered_map<int, int> prime;

while (n --) {
int x;
scanf("%d", &x);
for (int i = 2; i <= x/i; ++i) { //分解质因数
while (x % i == 0)
prime[i] ++, x /= i;
}
if (x > 1)
prime[x] ++;
}

ll res = 1;
for (auto i : prime)
res = res * (i.second+1) % mod;
//运用公式计算，注意每次算完都要取模，否则可能溢出

printf("%lld", res);

return 0;
}


### 题目描述

#### 样例

3
2
6
8


12


### 算法

（详情见 867 分解质因数 题解

#include <iostream>
#include <cstdio>
#include <unordered_map> //用哈希表存储质数

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

int main() {
int n;
scanf("%d", &n);

unordered_map<int, int> prime;

while (n --) {
int x;
scanf("%d", &x);
for (int i = 2; i <= x/i; ++i) { //分解质因数
while (x % i == 0)
prime[i] ++, x /= i;
}
if (x > 1)
prime[x] ++;
}

ll res = 1;
for (auto i : prime)
res = res * (i.second+1) % mod; //运用公式计算，注意每次算完都要取模，否则可能溢出

printf("%lld", res);

return 0;
}


#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5+5;

int fac[N];

int main() {
int n;
scanf("%d", &n);
while (n --) {
int t;
scanf("%d", &t);
int cnt = 0;
for (int i = 1; i <= t/i; ++i) {
if (t % i == 0) {
printf("%d ", i);
fac[cnt ++] = i;
}
}
for (int i = cnt-1; i >= 0; --i) {
if (fac[i] != t/fac[i])
printf("%d ", t/fac[i]);
}
printf("\n");
}
return 0;
}


### 题目描述

#### 样例

2
6
8


1 2 3 6
1 2 4 8


### 算法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
int t;
scanf("%d", &t);
while (t --) {
int n;
scanf("%d", &n);
vector<int> res;
for (int i = 1; i <= n/i; ++i) {
if (n % i == 0) {
res.push_back(i);
if (i != n/i)
res.push_back(n/i);
}
}
sort(res.begin(), res.end());
for (int i = 0; i < res.size(); ++i)
printf("%d ", res[i]);
puts("");
}
return 0;
}


#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e5+5;

int fac[N];

int main() {
int n;
scanf("%d", &n);
while (n --) {
int t;
scanf("%d", &t);
int cnt = 0;
for (int i = 1; i <= t/i; ++i) {
if (t % i == 0) {
printf("%d ", i);
fac[cnt ++] = i;
}
}
for (int i = cnt-1; i >= 0; --i) {
if (fac[i] != t/fac[i])
printf("%d ", t/fac[i]);
}
printf("\n");
}
return 0;
}


Jasper08
11天前
AC Saber是不是出bug了，我的胜率显示150%（