Problem Statement
|
|
NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.
You are given two geometric progressions S1 = (b1*q1i, 0 <= i <=
n1-1) and S2 = (b2*q2i, 0 <= i <=
n2-1). Return the number of distinct integers that belong to at least one of these progressions. |
Definition
|
|
Class: |
GeometricProgressions |
Method: |
count |
Parameters: |
int, int, int, int, int, int |
Returns: |
int |
Method signature: |
int count(int b1, int q1, int n1, int b2, int q2, int n2) |
(be sure your method is public) |
|
|
|
Constraints
|
- |
b1 and b2 will each be between 0 and 500,000,000, inclusive. |
- |
q1 and q2 will each be between 0 and 500,000,000, inclusive. |
- |
n1 and n2 will each be between 1 and 100,500, inclusive. |
Examples
|
0) |
|
|
|
Returns: 6
|
The progressions in this case are (3, 6, 12, 24, 48) and (6, 12, 24, 48, 96). There are 6 integers that belong to at least one of them: 3, 6, 12, 24, 48 and 96. |
|
|
1) |
|
|
|
Returns: 9
|
This time the progressions are (3, 6, 12, 24, 48) and (2, 6, 18, 54, 162). Each of them contains 5 elements, but integer 6 belongs to both progressions, so the answer is 5 + 5 - 1 = 9. |
|
|
2) |
|
|
|
Returns: 2
|
The progressions are (1) and (0). |
|
|
3) |
|
|
|
Returns: 100500
|
Each element of the second progression belongs to the first progression as well. |
|
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
【题解】
分解质因数后判断究竟是否相同。
只需以为枚举。
【代码】
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
int a[100][3],b[100][3],t[100][3];
class GeometricProgressions
{
public:
int count(int, int, int, int, int, int);
};
void prime(int a[][3],int &tot,int x,int y)
{
tot=0;
int i;
for (i=2;i*i<=max(x,y);i++)
{
if (x<=1 && y<=1) return;
if (x && x%i==0)
{
a[++tot][0]=i;
while (x%i==0)
{
x/=i;
a[tot][1]++;
}
}
if (y && y%i==0)
{
if (a[tot][0]!=i) a[++tot][0]=i;
while (y%i==0)
{
y/=i;
a[tot][2]++;
}
}
}
if (x<y)
{
if (x!=1)
a[++tot][0]=x,a[tot][1]=1;
if (y!=1)
{
if (a[tot][0]!=y) a[++tot][0]=y;
a[tot][2]=1;
}
}
else {
if (y!=1)
a[++tot][0]=y,a[tot][2]=1;
if (x!=1)
{
if (a[tot][0]!=x) a[++tot][0]=x;
a[tot][1]=1;
}
}
}
int GeometricProgressions::count(int b1, int q1, int n1, int b2, int q2, int n2)
{
int i,j,t1,t2,ans,tt;
bool ff;
if (b2==0 || q2<=1)
{
swap(b1,b2);swap(q1,q2);swap(n1,n2);
}
if (b1==0 || q1<=1)
{
set<long long> v;
v.insert(b1);
if (n1>0) v.insert(b1*q1);
long long cur=q2;
for (i=0;i<n2;i++)
{
v.insert(b2*cur);
cur*=q2;
if (cur>500000000)
return v.size()+n2-i-1;
}
return v.size();
}
prime(a,t1,q1,b1);
prime(b,t2,q2,b2);
ans=n1+n2;
if (t1!=t2) return ans;
for (i=1;i<=t1;i++)
if (a[i][0]!=b[i][0]) return ans;
if (b[1][1]==0)
{
swap(n1,n2);
memcpy(t,a,sizeof(a));
memcpy(a,b,sizeof(b));
memcpy(b,t,sizeof(t));
}
for (i=0;i<n1;i++)
{
tt=a[1][1]*i+a[1][2]-b[1][2];
if (tt%b[1][1]!=0) continue;
if (tt<0) continue;
tt/=b[1][1];
if (tt>=n2) continue;
ff=true;
for (j=2;j<=t1;j++)
if (a[j][1]*i+a[j][2]!=b[j][1]*tt+b[j][2])
{
ff=false;
break;
}
if (ff) ans--;
}
return ans;
}
int main()
{
GeometricProgressions a;
cout << a.count(3,4,100500,48,1024,1000);
}
分享到:
相关推荐
topcoder-srm Topcoder SRM竞赛解决方案 测试是使用kawigi edit构建的。
你可以通过这道题去了解Topcoder的题目以及比赛形式
topcoder的数学类算法题目。一个整数被称为k-smooth当且仅当它的最大素因子不大于k,给定N和K,计算出1 - N中有多少个整数是k-smooth。1 , 1 <= K <= 1000.
关于TopCoder的竞赛指导,不仅仅是SRM,还有Bug Race、软件比赛的资料,是我从网上收集的,大部分是中文的
TopCoder SRM程序 我尝试过的TopCoder SRM程序列表。 在大多数时候,比赛时间与我的工作/其他活动冲突,因此我对TopCoder不太活跃。 但是我尽力去参加比赛,因为这很有趣。 就像在任何在线比赛中所期望的那样,代码...
topcoder-srm 顶级编码器srm问题集锦
用于topcoder的第3方编辑器插件。
Topcoder软件比赛注册方法和平台使用 Topcoder算法大赛客户端安装流程 Topcoder算法大赛客户端登陆及使用 Topcoder算法大赛注册流程 Topcoder图形比赛注册方法和平台使用
适合topcoder新手
topcoder算法讲座ppt
topcoder竞赛的算法讲座ppt
TopCoder比赛登录使用的客户端,需要配置Java环境
Topcoder的Java客户端,安装前确定已经安装了JRE
TopCoder新手入门指南,一步步操作既可以了,然后开启您的Topcoder编程之旅吧。
topcoder arena,包含ContestAppletProd.jnlp,CodeProcessor.jar,FileEdit.jar,TZTester,运行需要jre环境
TopCoper SmartWordToy problem 解决方法,C++源码。 Problem Statement The toy company "I Can't Believe It Works!...Form: http://community.topcoder.com/stat?c=problem_statement&pm=3935&rd=6532
topcoder的比赛作品,编译通过的。可以放心使用。
topcoder入门,对想做tc,但又不知道怎么搞的很有帮助,我首先也不知道搞。
给新手提供的TopCoder注册方法和平台使用 十分详细
概述当前,该集合具有以下代码: SRM(单回合)待办事项清单问题类别比赛类型比赛编号分配等级点表示法SRM 152 1个3 BiChromeSky SRM 655 1个3 排列计数SRM 656 1个2个叉车卡车操作员SRM 656 1个3 变形SRM 660 1个3 ...