none

題目描述

阿湯同學(xué)最近剛學(xué)數(shù)論，他發(fā)現(xiàn)數(shù)論實(shí)在是太有趣了，于是他想讓你也感受一下數(shù)論的樂(lè)趣。現(xiàn)在他給你一個(gè)正整數(shù) N 和一個(gè)正整數(shù) M，要求你用 N 對(duì) M 進(jìn)行取余操作，即 N % M，記余數(shù)為 S。
但是他發(fā)現(xiàn)這樣好像并不能讓你感受到數(shù)論的樂(lè)趣，于是他想讓你在N 對(duì) M 取余操作的基礎(chǔ)上再求出這個(gè)余數(shù) S 能分解出多少個(gè)不同質(zhì)因數(shù)。

質(zhì)因數(shù)：質(zhì)因數(shù)在數(shù)論里是指能整除給定正整數(shù)的質(zhì)數(shù)，質(zhì)數(shù)就是只能整除 1 和本身的數(shù)，定義 2 是最小的質(zhì)數(shù)。

輸入描述:

從標(biāo)準(zhǔn)輸入讀入數(shù)據(jù)。
輸入包含多組數(shù)據(jù)，第一行一個(gè)整數(shù) T 代表數(shù)據(jù)組數(shù)。接下來(lái)依
次描述每組數(shù)據(jù)，對(duì)于每組數(shù)據(jù)：
第一行輸入正整數(shù) N，第二行輸入正整數(shù) M

【數(shù)據(jù)規(guī)模】
1≤N≤10^100
1≤M≤2^31-1

輸出描述:

輸出到標(biāo)準(zhǔn)輸出。
對(duì)于每組數(shù)據(jù)，輸出一行：
余數(shù) S 能分解出的不同質(zhì)因數(shù)的個(gè)數(shù)。

輸入

2
68
40
6
180

輸出

2
2

思路

輸入的N太大，爆long long。模擬取余

板子

• 模擬取余

for (int i = 0; i < len; i++) {yu = (yu * 10 + s[i] - '0') % m; }

• 分解質(zhì)因數(shù)

//分解質(zhì)因數(shù)并統(tǒng)計(jì)不同的個(gè)數(shù) int ans = 0; for (int i = 2; i <= sqrt(num); i++) {if (num % i == 0) {ans++;while (num % i == 0) num /= i;} } if (num > 1) ans++;

AC

#include<bits/stdc++.h> #define N 100005 #define mem(a, b) memset(a, b, sizeof(a)) #define ll long long using namespace std; int main() {int t;cin >> t;while (t--) {string s; ll m, yu = 0, ans = 0;cin >> s >> m;int len = s.length();for (int i = 0; i < len; i++) {yu = (yu * 10 + s[i] - '0') % m;}for (int i = 2; i <= sqrt(yu); i++) {if (yu % i == 0) {ans++;while (yu % i == 0) yu /= i;}}if (yu > 1) ans++;cout << ans << endl; } return 0; }

總結(jié)

以上是生活随笔為你收集整理的F - 阿汤的疑惑（模拟取余+分解质因数）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。