【Hankson 的趣味題】

可能我只適合這道題的50分

但還是要爭取一下的

我們知道對于\(gcd\)\(lcm\)有這樣的定義

\(a=\prod _{i=1}^{\pi(a)}p_i^{d_{i}}\)

\(b=\prod _{i=1}^{\pi(b)}p_i^{g_{i}}\)

那么則有

\(gcd(a,b)=\prod_{i=1}^{\pi(max(a,b))} p_i^{min(g_i,d_i)}\)

\(lcm(a,b)=\prod_{i=1}^{\pi(max(a,b))} p_i^{max(g_i,d_i)}\)

把上面的式子翻譯成漢語就是

如果我們將\(a,b\)質因數分解,那么對于\(a,b\)所有同一個質因子,指數較小的相乘得到的就是\(gcd(a,b)\),指數較大的相乘得到的就是\(lcm(a,b)\)

比如說\(12,8\)

我們分解質因數

\(12=2^2*3^1\)

\(8=2^3\)

所以\(gcd(12,8)=2^{min(2,3)}*3^{min(1,0)}=2^2=4\)

\(lcm(12,8)=2^{max(2,3)}*3^{max(1,0)}=2^3*3^1=24\)

于是有了這個性質,我們做這道題就比較簡單了

那我們的核心就是把\(a0,a1,b0,b1\)都分解質因數

之后對于相同的質因子我們都要討論一下他的指數,來推出\(x\)的指數

如果有解的話,這個指數必定是一個范圍,所以我們可以求出每個指數的范圍之后乘法原理得出答案

如果無解我們就中途判斷推出就好了

但是還有一個問題,我們分解質因數的話應該怎么分解,分解到一個什么范圍

我們知道整數還有一個一個性質:每個整數\(n\)至多有一個大于\(\sqrt{n}\)的質因子

盡管這里的數都很大,小于等于\(2E9\)但是我們只需要篩出\(1\)\(\sqrt{2E9}\)之間的質數,剩下的那個質因子我們特判就可以了

代碼

#include<iostream>
#include<cstdio>
#include<cmath>
#include<bitset>
#define LL long long
#define re register
#define maxn 50005
using namespace std;
int T;
int p[maxn],tot;
bitset<maxn> f;
LL a0,a1,b0,b1;
inline LL read()
{char c=getchar();LL x=0;while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
int main()
{T=read();f[1]=1;for(re int i=2;i<=maxn-5;i++){if(!f[i]) p[++tot]=i;for(re int j=1;j<=tot&&p[j]*i<=maxn-5;j++){f[p[j]*i]=1;if(i%p[j]==0) break;}}//歐拉篩,由于sqrt(2000000000)大概為45000,所以篩到50000就可以了while(T--){LL ans=1;int flag=0;a0=read();a1=read();b0=read();b1=read();for(re int i=1;i<=tot;i++){if(a0==1&&a1==1&&b0==1&&b1==1) break;int num1=0,num2=0,num3=0,num4=0;while(a0%p[i]==0) num1++,a0/=p[i];while(a1%p[i]==0) num2++,a1/=p[i];while(b0%p[i]==0) num3++,b0/=p[i];while(b1%p[i]==0) num4++,b1/=p[i];//統計這個質因子對應的指數應該是多少if(num1<num2||num3>num4) //如果這個a0質因子的指數小于a1的,那么就無解,因為a1的指數應該是最小的//如果這個b0質因子的指數大于b1的,那么就無解,因為b1的指數應該是最大的{flag=1;break;}if(num3<num4) //如果b0的指數小于b1的,說明x此時的指數應該為num4,所以此時對答案沒有貢獻,判斷是否有解之后退出{if(min(num4,num1)!=num2){flag=1;break;}continue;}if(num1>num2)//如果a0的指數大于a1的,說明x此時的指數應該為num2,所以此時對答案沒有貢獻,判斷是否有解之后退出{if(max(num2,num3)!=num4){flag=1;break;}continue;}if(num3<num1){flag=1;break;}ans=ans*(num3-num1+1);}if(!flag&&(a1!=1||a0!=1||b0!=1||b1!=1)){if(a1>a0) flag=1;if(b1<b0) flag=1;if(b1==b0&&b1!=1) ans<<=1;}if(!flag) cout<<ans<<endl;else puts("0");}
}

轉載于:https://www.cnblogs.com/asuldb/p/10207829.html

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/395563.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/395563.shtml
英文地址,請注明出處:http://en.pswp.cn/news/395563.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

C# 控件雙緩沖控制 ControlStyles 枚舉詳解

ControlStyles 枚舉.NET Framework 4指定控件的樣式和行為。 此枚舉有一個 FlagsAttribute 特性&#xff0c;通過該特性可使其成員值按位組合。 命名空間&#xff1a; System.Windows.Forms程序集&#xff1a; System.Windows.Forms&#xff08;在 System.Windows.Forms.dll …

協作機器人 ai算法_如果我們希望人工智能為我們服務而不是不利于我們,我們需要協作設計...

協作機器人 ai算法by Mariya Yao姚iya(Mariya Yao) 如果我們希望人工智能為我們服務而不是不利于我們&#xff0c;我們需要協作設計 (If we want AI to work for us — not against us — we need collaborative design) The trope “there’s an app for that” is becoming …

Shadow Brokers 公布 2.1 萬美元的 0day 訂閱服務

神秘黑客組織 Shadow Brokers 宣布將向支付 2.1 萬美元 0day 訂閱服務的個人公布最新一批的 NSA 工具&#xff0c;這一聲明給全世界的白帽子黑客或安全研究人員造成了一場倫理危機。 一方面&#xff0c;Shadow Brokers 此前釋出過創造出勒索軟件 WannaCry 的 NSA 工具&#xff…

linux awk 常見字符串處理

awk指定輸出列&#xff1a; awk {print $0} file #打印所有列awk {print $1} file #打印第一列 awk {print $1, $3} file #打印第一和第三列 cat file | awk {print $3, $1} #打印第三列和第一列&#xff0c;注意先后順序。 cat file | awk {print $3, $NF} #打印第三列…

oracle ldap 配置,ldap 安裝

一、安裝步驟1:配置yum源掛著盤鏡像時用到&#xff1a; 這里不做解釋;(yum clean all && yum makecache)2:安裝OpenLDAP組件1)安裝OpenLDAP組件命令如下:[rootgitea ~]# yum install openldap openldap-servers openldap-clients openldap-devel compat-openldap -ycom…

scp跨主機拷貝工具

參考&#xff1a;http://www.cnblogs.com/hitwtx/archive/2011/11/16/2251254.html SSH上A機&#xff0c;要將10.1.17.95機/tpdata/shell_script/下面的crontab.tar.gz文件拷貝到A機的當前文件夾下面&#xff1a; scp weblogic10.1.17.95:/tpdata/shell_script/crontab.tar.gz …

Google Chrome瀏覽器可能在您不知情的情況下破壞了您的測試

by Robert Axelsen羅伯特阿克森(Robert Axelsen) Google Chrome瀏覽器可能在您不知情的情況下破壞了您的測試 (Google Chrome might have broken your tests without you even knowing about it) My colleague just discovered that Chrome 58 (released April 19th) has sile…

Java 9 將采用新的版本字符串格式

在現有的版本編碼格式使用了兩年之后&#xff0c;從Java 9開始&#xff0c;Java版本方案將根據業內軟件版本編碼的最佳實踐進行修改。使用或解析Java版本字符串的應用程序開發人員要注意了&#xff0c;因為這種變化可以會影響他們的應用程序。 正如JEP 223所闡述的那樣&#xf…

oracle 表更新表,Oracle 更新表(另一張表)

JUC學習筆記--Thread多線程基礎實現多線程的兩種方法 java 實現多線程通過兩種方式1.繼承Thread類 ,2.實現Runnable接口 class Newthead extends Thread{ public void ru ...SharePoint中新創建的Web Application在瀏覽器中報404錯誤問題描述:在安裝完成SharePoint 2010后,進入…

jQuery(愛前端)

一 jQuery 簡介 官網&#xff1a;www.jquery.com 口號&#xff1a;寫更少的代碼&#xff0c;做更多的事情 jQuery 是一個快速、小型的、特性很多的JS庫&#xff0c;它把很多事兒都變得簡單。jQuery是免費的、開源的。 jQuery 是 DOM 編程領域的霸主&#xff0c;極大的簡化了原生…

跳過 centos部署 webpy的各種坑

用centos部署webpy發現的各種坑&#xff1a; 1、python 版本&#xff1a; 2、中文編碼&#xff1a; 3、web模塊路徑&#xff1a; 在命令行里輸入python&#xff0c;能import web&#xff0c;但是網站錯誤報告一直報告沒有找到web模塊&#xff0c;說明web模塊路徑有問題。python…

撰寫本文的所有基本React.js概念

Update: This article is now part of my book “React.js Beyond The Basics”.更新&#xff1a;本文現在是我的書《超越基礎的React.js》的一部分。 Read the updated version of this content and more about React at jscomplete.com/react-beyond-basics.在jscomplete.com…

CentOS 7 firewalld使用簡介

2019獨角獸企業重金招聘Python工程師標準>>> Centos升級到7之后&#xff0c;發現無法使用iptables控制Linuxs的端口&#xff0c;google之后發現Centos 7使用firewalld代替了原來的iptables。下面記錄如何使用firewalld開放Linux端口&#xff1a; 1.快速使用說明 開啟…

簡述java語言的特點

簡述java語言的特點&#xff1a; ① 簡單的特性 ② 面向對象的特性 ③ 分布式處理的特性 ④ 健壯的特性 ⑤ 結構中立的特性 ⑥ 安全特性 ⑦ 可移植的特性 ⑧ 解釋的特性 ⑨ 高性能的特性 ⑩ 多線程的特性 轉載于:https://www.cnblogs.com/qq1335…

php函數嵌套 作用域,javascript 嵌套的函數(作用域鏈)_javascript技巧

嵌套的函數(作用域鏈)當你進行函數的嵌套時&#xff0c;要注意實際上作用域鏈是發生變化的&#xff0c;這點可能看起來不太直觀。你可把下面的代碼置入firebug監視值的變化。var testvar window屬性;var o1 {testvar:1, fun:function(){alert(o1: this.testvaro1.fun();1o2.f…

【C#-枚舉】枚舉的使用

枚舉是用戶定義的整數類型。 namespace ConsoleApplication1 {/// <summary>/// 在枚舉中使用一個整數值&#xff0c;來表示一天的階段/// 如&#xff1a;TimeOfDay.Morning返回數字0/// </summary>class EnumExample{public enum TimeOfDay{Morning 0,Afternoon …

Elixir 初嘗試 5 -- 遇見Actor

Actor模型的定義 wiki如是說 The actor model in computer science is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent computation. In response to a message that it receives, an actor can: …

創建外部快照_快照事件:現在如何僅通過拍照即可創建日歷事件

創建外部快照by Arjun Krishna Babu通過Arjun Krishna Babu 快照事件&#xff1a;現在如何僅通過拍照即可創建日歷事件 (Snap Event: How you can now create calendar events just by taking a picture) Google just published my first Android app, Snap Event, in their P…

一個備份sql server文件.bak還原成兩個數據庫

一直對這個概念很模糊&#xff0c;今天具體一點。 備份文件只要是正常的.bak文件就好。 數據庫>還原數據庫 直接填寫還原之后的文件名就行。 用一份備份文件還原兩個一樣的庫&#xff0c;只是名稱不一樣。 轉載于:https://www.cnblogs.com/Ly426/p/10209825.html

linux服務器防病毒,Linux系統中你不需要防病毒?_服務器評論-中關村在線

誤區4&#xff1a;Linux是無病毒。Linux的安全性這么好&#xff0c;這是否意味著Linux是無病毒嗎&#xff1f;現實&#xff1a;Linux是非常安全&#xff0c;并不是沒有針對Linux方面的病毒。有許多針對Linux的已知病毒。但是幾乎所有的已知病毒對于Linux在本質上都是非破壞性的…