Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

推了一天公式,在这里抛转引玉

Posted by ar_dong at 2022-07-29 16:19:00 on Problem 1061
In Reply To:tui Posted by:ar_dong at 2022-07-29 16:17:29
总长度为L,起始位置为h,步长为s,经过处理l,h,s可以都为正整数,之后找到l和s的最大公约数,此公约数必为h的公约数,否则无解
得到如下公式
n*s=m*l+h(m,n为正整数).。。。。。。。。。。。。。。。。。。。。公式1
设l=kl*s+s1(kl为非负整数)
设h=kh*s-h1(kh为正整数)
n*s=m*(kl*s+s1)+kh*s-h1
n*s=m*kl*s+kh*s+m*s1-h1
(n-m*kl-kh)s+h1=m*s1
设n1=m;
设m1=(n-m*kl-kh)
设l1=s;
则
n1*s1=m1*l1+h1(和公式1相同)
实现递归
当s1==1时,
n1=h1;
m=n1;
根据公式1求n=(m*l+h)/s;


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator