首页 > 代码库 > ural 1907 Coffee and Buns
ural 1907 Coffee and Buns
1907. Coffee and Buns
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Planet Ataraxia is known for its education centers. The people who are expected to take high social positions in future are brought up in conditions of continuous training and supervision from the early age. Each education center is a small town with all the necessary utilities. During the construction of a center, a square area is chosen which is divided into equal sections each sized 100 × 100 meters. In each of these sections they build one building, which would become residential or academic. The outer perimeter of the center is fenced.
After a successful military operation in the Andromeda nebula the active colonization of habitable planets has started. The need for people able to take command and lead people to the new worlds has increased. Therefore, two new education centers should be built on Ataraxia. Discussion about the details of the project in the local administration is already underway for many days. During this time it was decided that the first center will consist of a2 sections and that the second one will consist of no more than n2 sections. The situation is complicated because, according to requirements of the antimonopoly legislation, construction works must be performed by at least two different companies, each of them must build an equal number of buildings and an equal number of 100-meters segments of the fence.
You are responsible for resupplying the administration office. You understand that while they are discussing the pros and cons of each possible size of the second center a lot of buns and coffee will be consumed, and it‘s time to buy them. So you‘d like to know how many different sizes of the second center will meet the requirements of antimonopoly legislation and, therefore, will be fully considered by the administration.
Input
The only line contains integers a and n (1 ≤ a ≤ 1012; 1 ≤ n ≤ 1018).
Output
Output an amount of different sizes of the second center meeting the requirements of antimonopoly legislation.
Sample
input | output |
---|---|
3 6 | 4 |
Hint
In this example it is possible to build the second center sized 3 × 3 or 6 × 6, delegating the construction to three different companies, or to build it sized 1 × 1 or 5 × 5, delegating the construction to two different companies.
题意: 题目说了那么多,其实最后题意很简单,给定一个a和n,求在1-n之间有几个数x,满足gcd(4(a+x),a^2+x^2)>1
思路,gcd(4(a+x),a^2+x^2)>1 可以得到 gcd(a+x,a^2+x^2)>1( 如果a+x 是偶数,4就是没有用的,如果a+x是奇数,那么a,x有一个为奇,一个
为偶,那么a^2+x^2就是奇数,那么4也是没有用的) 然后根据 gcd(a,b) = gcd(b,a%b) 得到 gcd(a+x,2*a*x) ( a^2+x^2 = (a+x)^2-2*a*x 模 a+x 等于 2*a*x )
接下来就是计算 gcd(a+x,2*a*x) > 1 了 如果 a是偶数,那么 还可以转化为 gcd(a+x ,a*x) > 1 ; 这里符合的就是 x 是 a 的因子的倍数;
如果 a是奇数 ,那么所有的 奇数都是符合的;还有就是 x是a任意一个因子的倍数(代码里面 n/2 的意思就是,我们取完 1-n 里面所有的奇数。剩下的就是求偶数里面的,
因为x是偶数,所以 2 是可以不要的,就和上面一样的求法)
a任意一个因子的倍数个数,这里用容斥定理求;
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>#include<vector>#include<set>#include<stack>#include<map>#include<ctime>#include<bitset>#define LL long long#define INF 999999#define maxn 500010using namespace std;LL get(LL n,LL MAX){ vector<LL>q; LL num=n,ans=0,tt ; for(LL i = 2 ; i*i <= n ;i++)if(n%i==0) { while(n%i==0) { n /= i ; } q.push_back(i) ; } if(n>1)q.push_back(n) ; int m = q.size(); int len=(1<<m) ,e ; for( int i = 1 ; i < len ;i++) { e=0; tt=1; for( int j = 0 ; j < m ;j++)if((1<<j)&i) { tt *= q[j] ; e++; } if(e&1) ans += MAX/tt ; else ans -= MAX/tt ; } return ans;}int main(){ int i,j,k; LL n ,a,ans ; while(cin >> a >> n) { if(a&1) ans=(n+1)/2 ,n/=2; else ans=0; ans += get(a,n) ; cout << ans<<endl; }}
ural 1907 Coffee and Buns
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。