LightOJ

admin管理员组

文章数量:1130349

LightOJ

题意

有一块矩形（也可能是正方形）的飞毯。

给定飞毯的面积\(n\)和最小可能的边长\(a\)，求可能有多少种不同边长的飞毯。（\(1<=a<=n<=1e12\)）

如面积\(n=6\)时，\(\{2,3\}\)和\(\{3,2\}\)算一种。

题解

本来想\(sqrt(n)\)的复杂度直接枚举\(n\)的所有因数，发现\(TLE\)了。

正解是把\(n\)质因数分解成\(n=a_1^{b_1}a_2^{b_2}...a_n^{b_n}\)，然后\(n\)的因子的个数就是\((1+b_1)*(1+b_2)...(1+b_n)\)。

我自做聪明的把上面得出的结果加上\(1\)（考虑到因子有\(1\)的情况），结果WA了一晚上。

得出\(n\)的因子个数之后，再暴力枚举小于\(b\)的数，如果是\(n\)的因数就减掉。

从理论上来说，两种方法的复杂度应该是相同的吧。后面的就能过，显然数据不靠谱。

代码

#include <bits/stdc++.h>#define FOPI freopen("in.txt", "r", stdin)
#define FOPO freopen("out.txt", "w", stdout)
#define FOR(i,x,y) for (int i = x; i <= y; i++)
#define ROF(i,x,y) for (int i = x; i >= y; i--)using namespace std;
typedef long long LL;
const int N = 1e6 + 10;int Prime[N+100];void getPrime(int N)
{memset(Prime, 0, sizeof(Prime));FOR(i, 2, N){if (!Prime[i]) Prime[++Prime[0]] = i;for (int j = 1; j <= Prime[0] && Prime[j] <= N/i; j++){Prime[Prime[j]*i] = 1;if (i % Prime[j] == 0) break;}}
}int factor[N+100][2];int facCnt;
LL Factor(LL x)
{facCnt = 0;LL tmp = x;for (int i = 1; Prime[i] <= tmp/Prime[i]; i++){factor[facCnt][1] = 0;if (tmp % Prime[i] == 0){factor[facCnt][0] = Prime[i];while(tmp % Prime[i] == 0){factor[facCnt][1]++;tmp /= Prime[i];}facCnt++;}}if (tmp != 1){factor[facCnt][0] = tmp;factor[facCnt++][1] = 1;}LL res = 1;FOR(i, 0, facCnt-1)res *= (1+factor[i][1]);return res;
}LL n, b;
int t;int main()
{getPrime(N);scanf("%d", &t);FOR(ca, 1, t){scanf("%lld %lld", &n, &b);if (n < b*b){printf("Case %d: 0\n", ca);continue;}LL Sum1 = Factor(n) / 2;FOR(i, 1, b-1)if (n % i == 0) Sum1--;printf("Case %d: %lld\n", ca, Sum1);}
}

转载于:.html

LightOJ

题意

有一块矩形（也可能是正方形）的飞毯。

给定飞毯的面积\(n\)和最小可能的边长\(a\)，求可能有多少种不同边长的飞毯。（\(1<=a<=n<=1e12\)）

如面积\(n=6\)时，\(\{2,3\}\)和\(\{3,2\}\)算一种。

题解

本来想\(sqrt(n)\)的复杂度直接枚举\(n\)的所有因数，发现\(TLE\)了。

正解是把\(n\)质因数分解成\(n=a_1^{b_1}a_2^{b_2}...a_n^{b_n}\)，然后\(n\)的因子的个数就是\((1+b_1)*(1+b_2)...(1+b_n)\)。

我自做聪明的把上面得出的结果加上\(1\)（考虑到因子有\(1\)的情况），结果WA了一晚上。

得出\(n\)的因子个数之后，再暴力枚举小于\(b\)的数，如果是\(n\)的因数就减掉。

从理论上来说，两种方法的复杂度应该是相同的吧。后面的就能过，显然数据不靠谱。

代码

#include <bits/stdc++.h>#define FOPI freopen("in.txt", "r", stdin)
#define FOPO freopen("out.txt", "w", stdout)
#define FOR(i,x,y) for (int i = x; i <= y; i++)
#define ROF(i,x,y) for (int i = x; i >= y; i--)using namespace std;
typedef long long LL;
const int N = 1e6 + 10;int Prime[N+100];void getPrime(int N)
{memset(Prime, 0, sizeof(Prime));FOR(i, 2, N){if (!Prime[i]) Prime[++Prime[0]] = i;for (int j = 1; j <= Prime[0] && Prime[j] <= N/i; j++){Prime[Prime[j]*i] = 1;if (i % Prime[j] == 0) break;}}
}int factor[N+100][2];int facCnt;
LL Factor(LL x)
{facCnt = 0;LL tmp = x;for (int i = 1; Prime[i] <= tmp/Prime[i]; i++){factor[facCnt][1] = 0;if (tmp % Prime[i] == 0){factor[facCnt][0] = Prime[i];while(tmp % Prime[i] == 0){factor[facCnt][1]++;tmp /= Prime[i];}facCnt++;}}if (tmp != 1){factor[facCnt][0] = tmp;factor[facCnt++][1] = 1;}LL res = 1;FOR(i, 0, facCnt-1)res *= (1+factor[i][1]);return res;
}LL n, b;
int t;int main()
{getPrime(N);scanf("%d", &t);FOR(ca, 1, t){scanf("%lld %lld", &n, &b);if (n < b*b){printf("Case %d: 0\n", ca);continue;}LL Sum1 = Factor(n) / 2;FOR(i, 1, b-1)if (n % i == 0) Sum1--;printf("Case %d: %lld\n", ca, Sum1);}
}

转载于:.html

本文标签： LightOJ